Frequent Number Revisited
Last year i blogged an interesting problem about finding the most frequent number in limited memory. I used a kinda complex divide-and-conquer method at that time to solve it.
Occasionally today, i found a much more elegant algorithm for this problem when reading the book Algorithms Design Techniques and Analysis.
The basic idea for this algo is:
If two different elements in the original sequence are removed, then the majority (aka the most frequent number) remains the majority in the new sequence.
So life becomes easier. We start by denoting the first element as the 'x', set a counter with value 1 for it, then scan the elements left one by one:
If it's the same as the 'majority', then increase the counter by one; otherwise, decrease the counter by one.
After all elements are scaned, if the counter is greater than zero, then x is just the answer. What's most important is that, whenever counter gets to be zero, we assign the next element as the new 'x'.
So to the original problem, we can apply the method above with an on-line algo. Final code runs in space O(1) and time O(n). Cheer for the power of algorithms. =)
