Boyer Moore Voting Algorithm

经典题目

169 Majority Element 229 Majority Element II

中心思想：抵消。

比如有5个A，6个B，那么B比A多1个，则用这多出来的1个B去进行接下去的计算。直到最后，多余的那几个candidate就是majority的竞争者。

public List<Integer> majorityElement(int[] nums) {
    List<Integer> res = new ArrayList<>();
    int candidate1 = 0;
    int candidate2 = 1;
    int times1 = 0;
    int times2 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == candidate1) {
            times1 += 1;
        } else if (nums[i] == candidate2) {
            times2 += 1;
        } else if (times1 == 0) {
            times1 += 1;
            candidate1 = nums[i];
        } else if (times2 == 0) {
            times2 += 1;
            candidate2 = nums[i];
        } else {
            times1 -= 1;
            times2 -= 1;
        }
    }
    times1 = 0;
    times2 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == candidate1) times1 += 1;
        if (nums[i] == candidate2) times2 += 1;
    }
    if (times1 > nums.length / 3) res.add(candidate1);
    if (times2 > nums.length / 3) res.add(candidate2);
    return res;
}