4 ms·
The Boyer–Moore majority algorithm [1] which allows you to find the majority element (if one exists) in an unsorted array in linear time and constant space. [1
by utopcell 8y ago
The Boyer–Moore majority algorithm [1] which allows you to find the majority element (if one exists) in an unsorted array in linear time and constant space.
[1] https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_v...
- utopcell 8y ago..and its generalization [2], which finds the (at most) k elements whose frequency is more than 1/(k+1) in the unsorted stream (k=1 being the majority algorithm in [1].) [2] https://www.cs.bgu.ac.il/~dinitz/Course/SS-12/Karp-frequent-el.pdf https://www.cs.bgu.ac.il/~dinitz/Course/SS-12/Karp-frequent-...