摩尔投票算法

起因

刷leetcode_169 数组tag的时候有道题

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

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

一般来讲大概第一反应是暴力算法,出现次数累加看谁超过了总数量的一半即可输出结果…方法可行可惜效率太低,时间复杂度达到O(n^2^),那有没有线性复杂度的解决办法.

Boyer-Moore 投票算法

少数服从多数的摩尔投票算法就是其中之一的解决之道

这里按照找众数的题来解释算法的实现过程:

nums:[1,1,2,1,2,2,2,1,2]

比如说该数组nums,显然众数是 2

首先我们设置一个候选众数,初始为第一个元素nums[0]

我们设置一个计数器count,初始值为1,其规则是遇到与候选众数相同的数是+1,不同-1

当count值为0时,我们让候选众数变为下一位,并将count重置为1,继续上述规则

[1,1,2,1,2 | 2,1,2]

分隔处为count归0时,此时候选众数变为下一位2,count值回到1

显然在这前面这一过程中,随着count值的递增递减到归0我们消耗了相同数量的非众数和众数

这是我认为投票算法最重要的思想,通过这样的往复,遍历结束后,最终候选众数即为该数组众数

代码实现

附上用C实现上述例子:

int majorityElement(int* nums, int numsSize){
    int count = 0,res = nums[0];
    int i = 0;
    while(i < numsSize){
        if (!count)
            res = nums[i];
        count += (nums[i] == res ? 1:-1);
        i++;
    }
    return res;
}

Asahi
2019.7.5
at 530