给定一个String数组,求K个出现最频繁的数。
记录一下查到的资料和思路:
1. 使用heap sorting, 先用hashmap求出单词和词频。需要额外建立一个class Node,把单词和词频都保存进去,对Node中的词频进行堆排序。Time Complexity - O(n * logk)
2. 使用index couting,也是先用hashmap求出单词和词频,再基于单词的词频进行Radix Sorting。 这种方法有很多细节还需要思考。 Time Complexity - O(n)
Reference:
http://www.capacode.com/string/k-most-frequent-items-with-linear-time-solution/
http://blog.csdn.net/v_july_v/article/details/7382693
http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/
http://yuanhsh.iteye.com/blog/2200539