Skip to main content

摩尔投票法

info

摩尔投票算法 (Boyer–Moore majority vote algorithm) 是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。 这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上； 在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素， 那么第一次的结果就可能是无效的随机元素。

实现思路​

  1. 定义一个计数变量 cnt = 0 和最终结果 ret
  2. 遍历数据列表, 对于元素 x
    • 若 cnt = 0 , ret = x
    • 若元素 x == ret 则 cnt += 1
    • 否则 cnt -= 1
  3. 返回 ret

代码实现​

public int majorityElement() {
    int[] nums = [1, 2, 3, 3, 3, 3, 4, 5];
    int cnt = 0;
    Integer ret = null;

    for (int num : nums) {
        if (cnt == 0) {
            ret = num;
        }
        cnt += (num == ret) ? 1 : -1;
    }
    return ret;
}

复杂度分析​

  • 时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
  • 空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

参考链接​