[LintCode] Majority Number III - Woodstock Blog
Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array. Find it.
Note: There is only one majority number in the array
Example: For [3,1,2,3,2,3,3,4,4,4] and k = 3, return 3
Analysis
Similar to 'Majority Number II', but a little more difficult.
Instead of keeping 2 value for checking, now keep k values. Since values are constantly checked for existance, using a HashMap looks like a great idea.
Another idea suggest by G4G is a mechanism similar to the famous Tetris Game. The size of the buffer is k. The buffer is full, we remove all items by counter of 1. When counter reach 0, remove that item. In this way, the elements left in the buffer are the majority numbers.
This method is also used in counting highly-frequent string keywrods. For example, another post [Design] Big Data – Real Time Top K discusses about it.
Read full article from [LintCode] Majority Number III - Woodstock Blog
No comments:
Post a Comment