2

这是m代码

Integer max = Collections.max(map.values());
int count = 20;
while(count>0)
{
    for (Map.Entry<String, Integer> e : map.entrySet())
        if(e.getValue() == max)
        {
            System.out.println(e.getKey() + "occurs" + e.getValue() + "times");
            count--;
        }
        max--;
}

该程序以 n 平方时间复杂度的 theta 运行。有没有更好的方法来显示 max 中按降序排列前 20 个最大值的条目？

4

2 回答 2

3

一般来说，除非你有证据表明性能很差，否则我会做最简单的事情。所以，首先，我会简单地对整个地图进行排序，然后遍历前 20 个元素，如下所示：

Map<?,?> mySortedMap = new TreeMap<?,?>(map);
Iterator<Entry<?,?>> entries = mySortedMap.entrySet().iterator();
for (int i = 0; i<20; i++) {
  System.out.println(entries.next());
}

不要过早优化。现在，如果您确实有性能问题，那么事情就会变得有趣。我将画出我要使用的算法。

  1. 创建一个大小为 20 的数组
  2. 以任意顺序遍历地图
  3. 如果地图的下一个值在目前看到的前 20 个中，则在适当的位置插入到数组中。

该算法具有更好的最坏情况和最佳情况运行时间 (theta(n))。

于 2013-09-04T19:18:01.977 回答
1

高效，O(n log 20)，在所有情况下都正确，并且不使用 JDK 之外的任何东西：

PriorityQueue<Map.Entry<String, Integer>> pq = 
  new PriorityQueue<Map.Entry<String, Integer>>(
    20, new Comparator<Map.Entry<String, Integer>() {
      @Override public int compare(
          Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
        return e2.getValue().compareTo(e1.getValue());
        // not the other way around, since we want the maximum values
      }
    });
for (Map.Entry<String, Integer> entry : map.entrySet()) {
  pq.add(entry);
  if (pq.size() > 20) {
    pq.remove();
  }
}
while (!pq.isEmpty()) {
  Map.Entry<String, Integer> entry = pq.remove();
  System.out.println("Key: " + entry.getKey() + " Value: " + entry.getValue());
}
于 2013-09-04T19:59:51.457 回答