[LeetCode]Majority Element

这道题用sort和hashmap都可以做。但是Moore Voting是可以达到O(n)时间常数空间的解法。基本思想是，总共n个数，找出现大于n/2次数的数，我们每次消去不同的一队，如果存在这个数，剩下的那个数就是我们要找的。否则就不存在。所以我们通过moore voting找打那个数之后，还有去原数组验证一遍（[1,2,3]的情况，我们最后保留的数是3，但其不是众数）。如果要找出现次数大于n/3的数的话，因为最多有可能有两个这样的数，所以我们保留两个candidate，每次消去三个不同的数，最后回原数组验证，以此类推。这道题保证有结果，所以我们不需要去原数组验证，代码如下：

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	int len = nums.size(), candidate = 0, count = 0;
	for(int i = 0; i < len; ++i)
	{
	int num = nums[i];
	if(!count)
	{
	candidate = num;
	++count;
	}
	else
	{
	if(num == candidate)
	++count;
	else
	--count;
	}
	}
	return candidate;
	}
	};

view raw Majority Element.cpp hosted with ❤ by GitHub