25.数组中出现次数超过一半的数字

// 26.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <vector>
#include <map>

using namespace::std;

class Solution {
public:
	int MoreThanHalfNum_Solution(vector<int> vec) {
		if (vec.empty()) return 0;

		int retVal = 0 ;
		QuickSort(vec, 0, vec.size() - 1);
		return vec[vec.size() / 2];
	}

	void QuickSort(vector<int> & vec, int l, int r) {
		int i = l;
		int j = r;
		int pivot = vec[(l + r) / 2];
		while (i - j <= 0)
		{
			if (vec[i] < pivot)
				i++;
			else if (vec[j] > pivot)
				j--;
			else
			{
				int temp = vec[i];
				vec[i] = vec[j];
				vec[j] = temp;
				i++; j--;
			}
		}
		if (l < j)
			QuickSort(vec, l, j);
		if (r > i)
			QuickSort(vec, i, r);
	}
	bool CheckHalf(vector<int> & vec) {
		int half = vec[vec.size() / 2];
		int count = 0;
		for (int i = 0; i < vec.size(); i++) {
			if (vec[i] == half) count++;
		}
		return count > vec.size() / 2 ? true : false;
	}
};
int _tmain(int argc, _TCHAR* argv[])
{
	vector<int> vec;
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(2);
	vec.push_back(2);
	vec.push_back(2);
	vec.push_back(5);
	vec.push_back(4);
	vec.push_back(2);

	Solution s;
	int result = s.MoreThanHalfNum_Solution(vec);
	return 0;
}