s4553711
8/15/2017 - 2:33 PM

229.cpp

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