I need to print the K most-used words from a text file containing N words in O(N) time complexity.
I have tried it using HashMap by taking the word as key and number of occurrence as value and then sorting it by values. But sorting the HashMap by values takes O(NlogN) which is more than my requirement.
If K = 10 then I need to print the 10 most used words from a text file.
You can't do sorting, because sorting is as O(NlogN), which apparently can not satisfy you.
Top k problem has the standard stereotype of solutions, which is O(N).
first, use a map to store the frequency. Iterate the list, calculate the frequency of words, then put them into the map.
Second, use a PriorityQueue to calculate the top k frequency, which has a volume of k. Iterate the map, put each entry into the PriorityQueue, if the size of the PriorityQueue is larger than k, then do the poll().
finally, the ProioritiyQueue contains the result of the top K frequency words.
