229.求众数II

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

输入：[3,2,3]
输出：[3]

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

输入：nums = [1]
输出：[1]

思路

• 哈希表记录出现的次数，这种空间复杂度不为O(1)

• 利用投票算法

投票算法的原理是通过不断消除不同元素直到没有不同元素，剩下的元素就是我们要找的元素。

TIP

抵消阶段：两个不同投票进行对坑，并且同时抵消掉各一张票，如果两个投票相同，则累加可抵消的次数；

计数阶段：在抵消阶段最后得到的抵消计数只要不为 0，那这个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数，才可确定。

摩尔投票法经历两个阶段最多消耗 O(2n) 的时间，也属于 O(n) 的线性时间复杂度，另外空间复杂度也达到常量级。

• 如果至多选一个代表，那他的票数至少要超过一半（⌊ 1/2 ⌋）的票数；
• 如果至多选两个代表，那他们的票数至少要超过 ⌊ 1/3 ⌋ 的票数；
• 如果至多选m个代表，那他们的票数至少要超过 ⌊ 1/(m+1) ⌋ 的票数。

解答

• 投票算法的模板

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    const len=nums.length
    if(len===0||len===1) return nums

    let count1=0,count2=0 //初始票数
    let candicate1=nums[0],candicate2=nums[1] //初始化候选人
    let ans=[]
    //摩尔投票过程
    for(let num of nums){
        if(num===candicate1){ //候选人1投票
            count1++
            continue
        }
        if(num===candicate2){ //候选人2投票
            count2++
            continue
        }
        if(count1===0){ //当候选人1票数为0时，无法再与其他候选人对抗，于是更换候选人
            candicate1=num
            count1++
            continue
        }
        if(count2===0){ //当候选人2票数为0时，无法再与其他候选人对抗，于是更换候选人
            candicate2=num
            count2++
            continue
        }

        //其他候选人与候选人1,2对抗
        count1--
        count2--
    }


    //重置候选人1，2的票数为0,为之后检票做准备
    count1=0
    count2=0

    //检票过程，判断候选人1，2的票数是否超过len/3
    for(let num of nums){
        if(num===candicate1) count1++
        if(num===candicate2) count2++
    }
    if(count1>Math.floor(len/3)) ans.push(candicate1)
    if(count2>Math.floor(len/3)) ans.push(candicate2)
    return [...new Set(ans)]
};

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

var majorityElement = function(nums) {
    let count = 1
    let result = nums[0]
    for(let i=1;i<nums.length;i++) {
        if(count === 0) {
            result = nums[i] // 更换候选人
        }
        if(nums[i] === result) {
            count++
        } else {
            count--
        }
    }
    return result
};