229. Majority Element II

problem description

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

algorithm analysis

这题是这个系列的第二题，第一题是求出一个占一半以上元素的主元素。

这里是得出其中两个。其实可以从第一题类似的方法衍生出来。

第一题用的类似投票的方法，由于肯定有一个数超过一半以上。如果当前当选元素和当前遍历到的元素一样，当选元素得票数加一。否则减一。如果为0，则换当选元素。由于有一半以上保证了为一个数，这个算法能选出一个主元素。

这一题有点不同，需要得到占1/3元素以上的数字。这里只保证肯定有答案。所以这里有两种情况，只有一个数和两个数。

首先我们来看如果利用第一题类似的投票机制。这里维护两个candidate，如果当前元素和其中一个candidate相等，就投一票。如果两个都不想等，两个候选者都减一票。

如何证明这里不会将超过1/3的candidate排除呢？ 这里至少有一个candidate超过1/3，所以还剩2/3，就算剩下部分全都不同，也只会有1/3次投票的时候，会将两个候选者的票数减去。还有1/3的情况时第二个候选者票数为0，被替代。所以这里肯定会有一个结果，可能有两个。最后的时候，要确认一下，是否两个candidate的票数超过1/3

code

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        if(nums.size()==0)
            return res;

        int candidate1=nums[0];
        int candidate2=nums[0];

        int count1=0;
        int count2=0;
        for(int i:nums){
            if(i==candidate1){
                count1++;
                continue;
            }
            if(i==candidate2){
                count2++;
                continue;
            }   

            if(count1==0){
                candidate1=i;
                count1=1;
                continue;
            }

            if(count2==0){
                candidate2=i;
                count2=1;
                continue;
            }

            count1--;
            count2--;
        }
        count1=0;
        count2=0;

        for(int i:nums){
            if(i==candidate1)
                count1++;
            else if(i==candidate2)
                count2++;
        }

        if(count1>nums.size()/3)
            res.push_back(candidate1);

        if(count2>nums.size()/3)
            res.push_back(candidate2);

        return res;

    }
};

algorithm analysis

时间复杂度O(n)，空间复杂度O(1)