什么数据结构应该用于高分列表？

可能重复：
How to sort a Map<Key, Value> on the values in Java?
how to sort Map values by key in Java 什么数据结构应该用于高分列表？

我试图跟踪得分，我需要能够没有得到密钥的成绩进入非升序排序并且不符合数值。我的第一个想法是使用地图，但我真的很难找到一种方法来保持按值排序的地图。这些值都是整数对象。我将如何去排序这样的高分榜？

2012-07-14 SaxSalute

这个职位似乎描述您的问题： [http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java] [1] [1]：http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java – EdgeCase 2012-07-14 23:39:56

这是一个微软/亚马逊工作面试类型的问题。您可以使用优先级队列作为队列的第一个元素，以获得最高分数。创建一个节点作为key | value对。按关键顺序由分数值维护并实现队列来实现它。

提供更多的细节

这是您的Node实现：

public class Node{ 

    private String name;  // the name 
    private double score;  // assuming you're using double 

    public Node(String name, double score){ 
     this.name = name; 
     this.score = score;   // assuming negative scores are allowed 
    } 
    public void updateScore(double score){ 
     this.score += score; 
    } 
}

而当你使用PriorityQueue，使Comparison根据得分值。如果你需要搜索/更新，它是O（1），根据Java API：

实现注意事项：此实现为提供O（日志（n））的时间入队和dequeing方法（报价， poll，remove（）和add）; 线性时间为remove（Object）和contains（Object）方法;和检索方法的恒定时间（peek，element和size）。

阅读API，我猜你可能需要覆盖Comparator<? super E> comparator()，或至少修改它以满足您的需求。这应该做到这一点。

来源

2012-07-14 23:33:05 cybertextron

这是一个有关排序地图的问题。 PriorityQueue如何相关？ – Bohemian 2012-07-14 23:37:01

@Bohemian不，不是。这是一个关于哪种数据结构最适合这项工作的问题。 OP简单地解释说他使用地图，而不是他_wants_基于地图的解决方案。 – kba 2012-07-14 23:39:02

我对如何使用PriorityQueue来排序整数值的同时仍然保持字符串的位置感到有点困惑。 – SaxSalute 2012-07-14 23:45:46

什么数据结构应该用于高分列表？

回答

相关问题