229. Majority Element II

[namespace-io]

摩尔投票的更一般写法

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
      
        int count1 = 0;
        int count2 = 0;
        int m1 = 0, m2 = 1;
        for(int i = 0; i < n; i++){
           
            if(m1 == nums[i]) count1++;
            else if(m2 == nums[i]) count2++;
            else if(count1 == 0){
                m1 = nums[i];
                count1++;
            } else if(count2 == 0){
                m2 = nums[i];
                count2++;
            } else {
                count1--;
                count2--;
            }
            
        }
        
        vector<int> ret;
        count1 = count2 = 0;
        for(int i = 0; i < n; i++){
            if(m1 == nums[i]) count1++;
            else if(m2 == nums[i]) count2++;
        }
        
        if(count1 > n/3) ret.push_back(m1);
        if(count2 > n/3) ret.push_back(m2);
        return ret;
    }
};

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int count1 = 0;
        int count2 = 0;
        int m1, m2;
        for(int i = 0; i < nums.size(); i++){
            if(count1 == 0 && m2 != nums[i]){
                count1 = 1;
                m1 = nums[i];
            } else if(count2 == 0 && m1 != nums[i]){
                count2 = 1;
                m2 = nums[i];
            } else {
                if(m1 == nums[i]) count1++;
                else if(m2 == nums[i]) count2++;
                else {
                    count1--;
                    count2--;
                }
            }
        }
        
        vector<int > ret;
        
        if(count1 != 0) {
            count1 = 0;
            for(int i = 0; i < nums.size(); i++) {
                if(m1 == nums[i]) count1++;
            }
            
            if(count1 > nums.size() / 3) ret.push_back(m1);
        }
        if(count2 != 0) {
            count2 = 0;
            for(int i = 0; i < nums.size(); i++) {
                if(m2 == nums[i]) count2++;
            }
            
            if(count2 > nums.size() / 3) ret.push_back(m2);
        }
        return ret;
    }
};