2021-10-22每日打卡--引申摩尔投票法

229. 求众数 II

今天的每日一题很简单，但是他的难度定义在“中等”，秒a了之后瑟瑟发抖的看题解区，秒a是挺爽的代码也挺少的，但是执行用时上太慢了，时间复杂度是O(n2)，这个时候就要想怎么提高性能了，题解看了一圈发现除了常规的map之外，还看到一个比较有意思的方法：摩尔投票法。

秒A代码：

    let res=[]
    let count
    num=Math.floor(nums.length/3)
    for(let i=0;i<nums.length;i++){
        count=0
        for(let j=0;j<nums.length;j++){
            if(nums[i]==nums[j]){
                count++
            }
        }
        if(count>num&&res.indexOf(nums[i])==-1)res.push(nums[i])
    }
    return res

摩尔投票法

解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。注意，是超出一半票数的那个人。

假设投票是这样的，[A, C, A, A, B]，ABC 是指三个候选人。

第一张票与第二张票进行对坑，如果票不同则互相抵消掉；

接着第三票与第四票进行对坑，如果票相同，则增加这个候选人的可抵消票数；

这个候选人拿着可抵消票数与第五张票对坑，如果票不同，则互相抵消掉，即候选人的可抵消票数 -1。

摩尔解题思路

理解摩尔投票法之后，我们再回到题目描述，题目可以看作是：在任意多的候选人中，选出票数超过⌊ 1/3 ⌋的候选人。
根据题意可知也就是最多只有2个候选人超过⌊ 1/3 ⌋的候选人。
我们可以这样理解，假设投票是这样的 [A, B, C, A, A, B, C]，ABC 是指三个候选人。

第 1 张票，第 2 张票和第3张票进行对坑，如果票都不同，则互相抵消掉；

第 4 张票，第 5 张票和第 6 张票进行对坑，如果有部分相同，则累计增加他们的可抵消票数，如 [A, 2] 和 [B, 1]；

接着将 [A, 2] 和 [B, 1] 与第 7 张票进行对坑，如果票都没匹配上，则互相抵消掉，变成 [A, 1] 和 `[B, 0] 。

代码：

var majorityElement = function(nums) {
    let len=nums.length
    let res=[]
    let map=Math.floor(len/2)//计算判断是多数元素的基准次数
    if(len==0||len==1)return nums
    let count1=0,count2=0;
    let c1=nums[0],c2=nums[1]
    for(let num of nums){
        if(num==c1){
            count1++
            continue
        }
        if(num==c2){
            count2++
            continue
        }
        if(count1==0){
            c1=num
            count1++
            continue
        }
        if(count2==0){
            c2=num
            count2++
            continue
        }
        count1--
        count2--
    }
 //重置候选人1，2的票数为0,为之后检票做准备
    count1=0,count2=0
//检票过程，判断候选人1，2的票数是否超过len/3
    for(let num of nums){
        if(c1==num){
            count1++
        }
        if(c2==num){
            count2++
        }
    }
    if(count1>map)res.push(c1)
    if(count2>map)res.push(c2)
    return [...new Set(res)]
};

摩尔投票法同类题👇，问题难点在于时间复杂度为O(n)以及空间复杂度是O(1)，map的做法空间复杂度是O(n)，这次我学习了他的做法用在上面

169. 多数元素

用摩尔投票法实现

解题思路

根据题意大于⌊ 1/2 ⌋的元素可知：“多数元素”的个数> ⌊ n/2 ⌋，其余元素的个数总和<= ⌊ n/2 ⌋。也就是说最多只有1个元素出现次数大于超过⌊ 1/2 ⌋的元素，因此只需要一个参数位。
投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。
因此“多数元素”的个数 - 其余元素的个数总和的结果肯定 >= 1。
这就相当于每个“多数元素”和其他元素两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。

代码:

var majorityElement = function(nums) {
    let len=nums.length
    let res=[]
    let map=Math.floor(len/2)
    if(len==0||len==1)return nums
    let count1=0
    let c1=nums[0]
    for(let num of nums){
        if(num==c1){
            count1++
            continue
        }
        if(count1==0){
            c1=num
            continue
        }
        count1--
    }
    count1=0
    for(let num of nums){
        if(c1==num)count1++     
    }
    if(count1>map)res.push(c1)
    return [...new Set(res)]
};

摩尔投票法复杂度分析

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

map法复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

最后编辑于：2021.10.22 02:38:04