找数组中出现次数大于一半的数字

MajorityNumber.cpp

/*
快排的思想，找到中位数上的数字，当数字左边数均小于，右边数均大于，位置在中间时，则是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;
	}
};

MajorityNumber2.cpp

/*
出现次数过半，把不同的两个数不断抵消掉，O(n)时间复杂度，O(1)空间复杂度
*/
class Solution {
public:
	int majorityElement(vector<int>& nums) {
		if (nums.size() == 0) return 0;
		int res = nums[0];
		int times = 1;
		for (auto num: nums) {
			if (times == 0) {
				res = num;
				times = 1;
			}
			else if (num == res) times++;
			else times--;
		}
		return res;
	}
};