【数组】Majority Element II

Dear 丶 2022-09-25 07:28 106阅读 0赞

题目：

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 ⌋的数。

我们注意到这样一个现象： 在任何数组中，出现次数大于该数组长度一半的值只能有一个。 通过数学知识，我们可以证明它的正确性，但是这并不在我们这篇博客里涉及。摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。那么有没有可能出现最后有两种或两种以上元素呢？根据定义，这是不可能的，因为如果出现这种情况，则代表我们可以继续一轮投票。因此，最终只能是剩下零个或一个元素。在算法执行过程中，我们使用常量空间实时记录一个候选元素c以及其出现次数f(c)，c即为当前阶段出现次数超过半数的元素。根据这样的定义，我们也可以将摩尔投票法看作是一种动态规划算法。

接着，我们来看我们今天要解决的问题。

这道题让我们求出现次数大于⌊ n/3 ⌋的众数，而且限定了时间和空间复杂度，那么就不能排序，也不能使用哈希表，这么苛刻的限制条件只有一种方法能解了，那就是摩尔投票法 Moore Voting，这种方法在之前那道题Majority Element 求众数中也使用了。题目中给了一条很重要的提示，让我们先考虑可能会有多少个众数，经过举了很多例子分析得出，任意一个数组出现次数大于n/3的众数最多有两个，具体的证明我就不会了，我也不是数学专业的。那么有了这个信息，我们使用投票法的核心是找出两个候选众数进行投票，需要两遍遍历，第一遍历找出两个候选众数，第二遍遍历重新投票验证这两个候选众数是否为众数即可，选候选众数方法和前面求众数一样，由于之前那题题目中限定了一定会有众数存在，故而省略了验证候选众数的步骤，这道题却没有这种限定，即满足要求的众数可能不存在，所以要有验证。

/** * @param {number[]} nums * @return {number[]} */
    var majorityElement = function(nums) {
        var a,b,countA=0,countB=0;
        for(var i=0,len=nums.length;i<len;i++){
            if(nums[i]==a){
                countA++;
            }else if(nums[i]==b){
                countB++;
            }else if(countA==0){
                countA=1;
                a=nums[i];
            }else if(countB==0){
                countB=1;
                b=nums[i]
            }else{
                countA--;
                countB--;
            }
        }
    
        countA=0;
        countB=0;
        for(var i=0,len=nums.length;i<len;i++){
            if(nums[i]==a){
                countA++;
            }
            if(nums[i]==b){
                countB++;
            }
        }
    
        var res=[];
        if(countA>Math.floor(len/3)){
            res.push(a);
        }
        if(countB>Math.floor(len/3)){
            res.push(b);
        }
    
        return res;
    
    };