microposts/boyer-moore.md


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---
date: 2018-06-04
---

The [Boyer-Moore algorithm for finding the majority of a sequence of elements](https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm) falls in the category of "very clever algorithms".

    int majorityElement(vector<int>& xs) {
        int count = 0;
        int maj = xs[0];
        for (auto x : xs) {
            if (x == maj) count++;
            else if (count == 0) maj = x;
            else count--;
        }
        return maj;
    }