229. 求众数 II（JS实现）

墨蓝 2022-11-27 12:27 228阅读 0赞

## 1 题目 ##

> 给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。  
> 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。  
> 示例 1:  
> 输入: \[3,2,3\]  
> 输出: \[3\]  
> 示例 2:  
> 输入: \[1,1,1,3,3,2,2,2\]  
> 输出: \[1,2\]

链接：https://leetcode-cn.com/problems/majority-element-ii

## 2 思路 ##

**这道题用摩尔投票法进行解答，根据题意我们知道超过1/3的出现次数这样的数，最多出现两个，因此设置两个变量，遍历整个数组进行投票**

## 3代码 ##

/** * @param {number[]} nums * @return {number[]} */
    var majorityElement = function(nums) { 
        let len = nums.length;
    
        if (len === 0 || len === 1) return nums;
    
        let num1 = num2 = nums[0];
        let count1 = count2 = 0;
    
        for (let num of nums) { 
            if (num === num1) {      //如果数字相同，得一票
                count1++;
                continue;
            }
    
            if (num === num2) {    //如果数字相同，得一票
                count2++;
                continue;
            }
    
            if (count1 === 0) { 
                num1 = num;
                count1++;
                continue;
            }
    
            if (count2 === 0) { 
                num2 = num;
                count2++;
                continue;
            }
    
            count1--;     //数字不同，则减一票
            count2--;    //数字不同，则减一票
        }
    
        count1 = count2 = 0;
        for (let num of nums) { 
            if (num === num1) count1++;
            if (num === num2) count2++;
        }
    
        const res = [];
    
        if (count1 > len / 3) res.push(num1);
        if (count2 > len / 3 && num1 !== num2) res.push(num2); 
    
        return res;
    };