[LeetCode]Majority Element II

做法同Majority Element，在链接的文章已经讲了，我们要保留两个candidate，每次消去三个不同的数。这道题没有保证一定存在满足条件的数，所以我们要回去验证，时间复杂度O(n)，常数空间复杂度，代码如下：

	class Solution {
	public:
	vector<int> majorityElement(vector<int>& nums) {
	int len = nums.size();
	unordered_map<int, int> map;
	for(int i = 0; i < len; ++i)
	{
	int num = nums[i];
	if(map.size() <= 1 || map.find(num) != map.end())
	++map[num];
	else
	{
	auto iter = map.begin();
	while(iter != map.end())
	{
	if(--(iter->second) == 0)
	map.erase(iter++);
	else
	++iter;
	}
	}
	}
	//check if elements in map are majoirity elements
	vector<int> res;
	for(auto& p : map)
	p.second = 0;
	for(int i = 0; i < len; ++i)
	if(map.find(nums[i]) != map.end())
	++map[nums[i]];
	for(auto& p : map)
	if(p.second * 3 > len)
	res.emplace_back(p.first);
	return res;
	}
	};

view raw Majority Element II.cpp hosted with ❤ by GitHub