aboutsummaryrefslogtreecommitdiff
path: root/microposts/boyer-moore.org
blob: 8c67b749551a02c5764af6933db0f41ea6d5c166 (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_src c++
  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_src