[leetcode]229. Majority Element II -- JavaScript 代码

淩亂°似流年 2022-09-25 07:16 121阅读 0赞

/** * @param {number[]} nums * @return {number[]} */
    var majorityElement = function(nums) {
        var ret = [];
        var len = nums.length;
        var threshold = len/3;
        if(len===0||len==1){
            return nums;
        }
        var candidate0 = nums[0];
        var candidate1 = Infinity;
        var count0 = 1;
        var count1 = 0;
        for(var i=1;i<len;i++){
            var tmp = nums[i];
            if(tmp == candidate0){
                count0++;
            }else if(tmp == candidate1){
                count1++;
            }else{
                if(count1 === 0){  
                    candidate1 = nums[i];  
                    count1++;  
                }else if(count0 === 0){  
                    candidate0 = nums[i];  
                    count0++;  
                }else{  
                    count0--;  
                    count1--; 
                }
            }
        }
        count0 = 0;
        count1 = 0;
        for(i=0;i<len;i++){
            if(nums[i]==candidate0){
                count0++;
            }
            if(nums[i]==candidate1){
                count1++;
            }
        }
        if(count0>threshold){
            ret.push(candidate0);
        }
        if(count1>threshold&&candidate1!=candidate0){
            ret.push(candidate1);
        }
        return ret;
    };

这道题的难点在于，1、要求 O(1) 的空间复杂度；2、并不保证Majority Element一定存在。

主体的思路和Majority Element是一样的，首先要从数组中找出备选众数。然后进行第二轮查找，确定备选众数能不能真正达到众数的标准。如果能，才能添加到将要返回的数组中。