blob: 629845436971034acb00915513ad06e6daabeb3b (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#+title: boyer-moore
#+date: <2018-06-04>
The
[[https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm][Boyer-Moore
algorithm for finding the majority of a sequence of elements]] falls in
the category of "very clever algorithms".
#+begin_example
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;
}
#+end_example
|
