3 ms·

Direct link to the pre-generalized: https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html N

Direct link to the pre-generalized: https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html Note that this algorithms fails silently if there is not majority element, which limits the scope of its utility. I assume that the reason it took so long to discover is that no one needed the solution before. Are there applications that can benefit form this algorithm?

beder 14y ago
You can do a second pass over the list to check that your solution is actually a majority element. This maintains the linear time and constant space properties.
- justincormack 14y ago
  Unfortunately single pass is usually the binding constraint eg real time data processing.