目录

  1. Boyer-Moore 投票算法

Boyer-Moore 投票算法

此算法也称为摩尔投票算法，用来计算众数。算法的核心思想在于：既然一个数是众数，必然在一个数组中占据绝大部分，数组中的每一个数字都代表一队人马，假设所有人马都势均力敌，那么混战情况下，只能是人多的胜利。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int moore(int[] nums) {
    int count = 0;
    Integer candidate = null;

    for (int num : nums) {
        if (count == 0) {
            //在此之前所有的人马已经消失殆尽，选择当前元素为关注势力（候选众数）
            candidate = num;
        }
        //moore 算法核心，只要当前数字和认为的众数相同，我方势力+1，否则我方势力-1，人马进行火并
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}