Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
分析：
本题是169.Majority Element的扩展，需要两次遍历，第一次遍历选出两个候选众数，第二次求出两个众数的出现次数，最后返回出现大雨n/3的众数。
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int num = nums.size();
int major0 = 0, major1 = 0, count0 = 0, count1 = 0;
for(int i = 0; i < num; ++i)
{
if(major0 == nums[i])
count0++;
else if(major1 == nums[i])
count1++;
else if(count0 == 0)
{
major0 = nums[i];
count0++;
}else if(count1 == 0)
{
major1 = nums[i];
count1++;
}else
{
count0--;
count1--;
}
}
count0 = 0, count1 = 0; //出现次数重新置0，第二次遍历重新求出现次数
for(int i = 0; i < num;++i)
{
if(nums[i] == major0) count0++;
else if(nums[i] == major1) count1++;
}
vector<int> ret;
if(count0 > num/3) ret.push_back(major0);
if(count1 > num/3) ret.push_back(major1);
return ret;
}
};
