Majority Element(I & II)

记住格式：

Majority Element I：
candidate = nums[0], cnt = 1, 相同加，不同减。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if(nums.empty()) return 0;
        int candidate = nums[0];
        int cnt = 1;
        for(int i=1; i<nums.size(); i++){
            if(nums[i] == candidate) cnt++;
            else{
                cnt--;
                if(cnt == 0){
                    candidate = nums[i];
                    cnt = 1;
                }
            }
        }
        return candidate;
    }
};

Majority Element II：
candidate1 = candidate2 = nums[0]
cnt1 = 1, cnt2 = 0;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.empty()) return vector<int>();
        int candidate1 = nums[0], candidate2 = nums[0];
        int cnt1 = 1, cnt2 = 0;
        
        for(int i=1; i<nums.size(); i++){
           if(cnt1 > 0 && nums[i] == candidate1){
               cnt1++;
           }else if(cnt2 > 0 && nums[i] == candidate2){
               cnt2++;
           }else if(cnt1 == 0){
               candidate1 = nums[i];
               cnt1 = 1;
           }else if(cnt2 == 0){
               candidate2 = nums[i];
               cnt2 = 1;
           }else{
               cnt1--; cnt2--;
           }
        }
        vector<int> ret;
        cnt1 = 0; cnt2 = 0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] == candidate1) cnt1++;
            else if(nums[i] == candidate2) cnt2++;
        }
        if(cnt1 > nums.size()/3) ret.push_back(candidate1);
        if(cnt2 > nums.size()/3) ret.push_back(candidate2);
        return ret;
    }
};