diff options
author | Yuchen Pei <me@ypei.me> | 2021-06-18 12:58:44 +1000 |
---|---|---|
committer | Yuchen Pei <me@ypei.me> | 2021-06-18 12:58:44 +1000 |
commit | 147a19e84a743f1379f05bf2f444143b4afd7bd6 (patch) | |
tree | 3127395250cb958f06a98b86f73e77658150b43c /microposts/boyer-moore.org | |
parent | 4fa26fec8b7e978955e5630d3f820ba9c53be72c (diff) |
Updated.
Diffstat (limited to 'microposts/boyer-moore.org')
-rw-r--r-- | microposts/boyer-moore.org | 21 |
1 files changed, 21 insertions, 0 deletions
diff --git a/microposts/boyer-moore.org b/microposts/boyer-moore.org new file mode 100644 index 0000000..6298454 --- /dev/null +++ b/microposts/boyer-moore.org @@ -0,0 +1,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 |