229. Majority Element II

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;
        
    }
};