获取TreeMap中的三个最高值

本文介绍了获取TreeMap中的三个最高值的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图在TreeMap中找到三个最高值。我编写了一个代码，但是我想问一下你是否可以建议一个更有效的方法。 基本上，我在TreeMap中保存文本的每个单词以及它在文本中出现的次数。然后我使用比较器对值进行排序。然后我迭代新创建的Map，直到我到达最后三个值，这是排序后的最高值并打印出来。我将使用大文本，所以这不是一个很好的方法。 这是我的代码：

I am trying to find the three highest values in a TreeMap. I wrote a code that is kind of doing it, but I would like to ask whether you can suggest a more efficient way. Basically, I am saving each word of my text in a TreeMap along with the number of times it appears in the text. Then I am using a comparator to sort the values. Then I am iterating through the newly created Map until I reach the last three values, which are the highest values after the sorting and print them out. I am going to use large texts, so this is not a very good way. Here is my code:

class Text{ public static void main(String args[]) throws FileNotFoundException, IOException{ final File textFile = new File("C://FileIO//cinderella.txt"); final BufferedReader in = new BufferedReader(new FileReader(textFile)); final TreeMap<String, Integer> frequencyMap = new TreeMap<String, Integer>(); String currentLine; while ((currentLine = in.readLine()) != null) { currentLine = currentLine.toLowerCase(); final StringTokenizer parser = new StringTokenizer(currentLine, " \t\n\r\f.,;:!?'"); while (parser.hasMoreTokens()) { final String currentWord = parser.nextToken(); Integer frequency = frequencyMap.get(currentWord); if (frequency == null) { frequency = 0; } frequencyMap.put(currentWord, frequency + 1); } } System.out.println("This the unsorted Map: "+frequencyMap); Map sortedMap = sortByComparator(frequencyMap); int i = 0; int max=sortedMap.size(); StringBuilder query= new StringBuilder(); for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) { Map.Entry<String,Integer> entry = (Map.Entry<String,Integer>) it.next(); i++; if(i<=max && i>=(max-2)){ String key = entry.getKey(); //System.out.println(key); query.append(key); query.append("+"); } } System.out.println(query); } private static Map sortByComparator(TreeMap unsortMap) { List list = new LinkedList(unsortMap.entrySet()); //sort list based on comparator Collections.sort(list, new Comparator() { public int compare(Object o1, Object o2) { return ((Comparable) ((Map.Entry) (o1)).getValue()) pareTo(((Map.Entry) (o2)).getValue()); } }); //put sorted list into map again Map sortedMap = new LinkedHashMap(); for (Iterator it = list.iterator(); it.hasNext();) { Map.Entry entry = (Map.Entry)it.next(); sortedMap.put(entry.getKey(), entry.getValue()); } return sortedMap; } }

推荐答案

我将使用哈希映射计算频率，然后将它们全部循环，选择前3个。您可以通过这种方式最小化比较，而不必进行排序。使用选择算法

I would count the frequencies with a hash map, and then loop over them all, selecting the top 3. You minimize comparisons this way, and never have to sort. Use the Selection Algorithm

-edit ，维基百科页面详述了选择算法的许多不同实现。具体来说，只需使用有界优先级队列，并将大小设置为3.不要花哨并将队列实现为堆或任何东西。只需使用数组。

-edit, the wikipedia page details many different implementations of the selection algorithm. To be specific, just use a bounded priority queue, and set the size to 3. Dont get fancy and implement the queue as a heap or anything. just use an array.