[LeetCode] Majority Element II

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. 

解题思路:

此前做了一道题目,返回主要元素,其中主要元素的定义是出现次数大于n/2的元素。当初投票法非常不错。类似的,这道题也可以用投票法,但是稍微复杂一下。注意到,对于一个数组来说,大于n/3的元素最多有2个。于是可以用两个变量来记录出现的候选主要元素。

设候选主要元素为can1,can2,其票数分别是count1,count2(初始化均为0)。逐个扫描nums内的元素nums[i],分情况讨论。

1、假设还未统计任何数,即count1=0&&count2=0,则can1=nums[i],count1=1

2、can1和can2其中一个没有初始化(设can2,即count2=0),且nums[i]!=can1,那么can2=nums[i],count2=1。对称另一种情况容易知道。

3、假设can1和can2两个都初始化了(count1!=0并且count2!=0),但是can1!=nums[i]并且can2!=nums[i]。那么count1和count2均减1

4、若count1!=0并且can1==nums[i],那么count1++。同样,若count2!=0并且can2==nums[i],那么count2++。

最后,验证can1和can2的出现次数即可。

下面是代码:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> result;
        
        int len = nums.size();
        int can1=0, count1 = 0, can2 = 0, count2 = 0;
        for(int i=0; i<len; i++){
            if(count1 == 0 && count2 == 0){
                can1 = nums[i];
                count1=1;
            }else if(count1!=0 && count2!=0 && can1!=nums[i] && can2!=nums[i]){
                count1--;
                count2--;
            }else if(can1==nums[i] && count1!=0){
                count1++;
            }else if(can2==nums[i] && count2!=0){
                count2++;
            }else if(count1==0&&count2!=0&&can2!=nums[i]){
                can1 = nums[i];
                count1++;
            }else if(count2==0&&count1!=0&&can1!=nums[i]){
                can2 = nums[i];
                count2++;
            }
        }
        
        //这两个只是候选的
        if(count1!=0){
            count1 = 0;
            for(int i=0; i<len; i++){
                if(can1==nums[i]){
                    count1++;
                }
            }
            if(count1>len/3){
                result.push_back(can1);
            }
        }
        if(count2!=0){
            count2 = 0;
            for(int i=0; i<len; i++){
                if(can2==nums[i]){
                    count2++;
                }
            }
            if(count2>len/3){
                result.push_back(can2);
            }
        }
        
        return result;
    }
};


0 条评论

    发表评论

    电子邮件地址不会被公开。 必填项已用 * 标注