/*
快排的思想，找到中位数上的数字，当数字左边数均小于，右边数均大于，位置在中间时，则是majority
*/
class Solution {
public:
	int majorityElement(vector<int>& nums) {
		int length = nums.size();
		int low = 0;
		int high = length - 1;
		while (low <= high) {
			int base = nums[low];
			int i = low;
			int j = high;
			while (i < j) {
				while (i< j && nums[j] >= base) j--;
				if (i < j) nums[i] = nums[j];
				while (i < j && nums[i] <= base) i++;
				if (i < j) nums[j] = nums[i];
				if (i == j && i == (length-1) / 2) return base;
			}
			nums[i] = base;
			if (i < length / 2) low = i + 1;
			else high = i -1;
		}
		return 0;
	}
};