> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/advanced-algorithm/boyer-moore-voting-algorithm.md).

# Boyer Moore Voting Algorithm

## 经典题目

[*169 Majority Element*](https://leetcode.com/problems/majority-element/description/)\
[*229 Majority Element II*](https://leetcode.com/problems/majority-element-ii/description/)

中心思想：抵消。

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

```java
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;
}
```