摩尔投票算法

问题背景

本文是根据LeetCode第169题"多数元素（如下图）"的要求，我们需要找到一个数组中出现次数超过⌊n/2⌋的元素。题目保证数组非空且这样的元素一定存在。

摩尔投票算法详解

算法思想

摩尔投票算法(Boyer-Moore Voting Algorithm)通过"对抗抵消"的方式找出多数元素：

1. 初始化候选元素和计数器
2. 遍历数组：
   • 相同元素则增加计数
   • 不同元素则减少计数
   • 计数归零时更换候选元素
3. 最后的候选元素即为多数元素

核心思想

我们先观察题目所给的两个示例：[3,2,3]和[2,2,1,1,1,2,2]并且该元素需要符合自身数量>数组长度/2，在这个条件之下，我们很容易就发现了：第一组中的元素3和第二组中的元素2，他们的数量是一定会大于其他元素的数量之和的。再者，n>0，所以n/2>0也是必定成立的，所以我们有了以下的代码。

代码实现

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        
        return candidate;
    }
}

原理详解

​示例1：[3,2,3]​​

​示例2：[2,2,1,1,1,2,2]​​

我们这里使用的是增强for和三元运算符来简化了代码，如果有小伙伴觉得不好懂的话，可以看看下面的这段代码

public class Solution  {
    public static int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {        //首先判断票数，0->初始化candidate和count
                candidate = nums[i]; //将当前元素赋值给candidate
                count = 1;
            } else if (nums[i] == candidate) {    //找到后面有相同的元素，票数+1
                count++;
            } else {
                count--;    //否则，票数-1
            }
        }
        
        return candidate;   //最后返回candidate
    }

详细的过程就不多说了，已经在上面的代码界面标明了注释。