java - 我应该为高分列表使用什么数据结构？

Question

可能重复：
如何对 Java 中的值对 Map<Key, Value> 进行排序？
如何在 Java 中按键对 Map 值进行排序

我正在尝试跟踪分数，并且我需要能够将分数排序为非升序，而不会使键和值脱节。我的第一个想法是使用地图，但我真的很难找到一种方法来保持地图按价值排序。这些值都是整数对象。我将如何对这样的高分列表进行排序？

Answer 1

这是一个微软/亚马逊求职面试类型的问题。您可以使用优先级队列，或者将最高分作为队列的第一个元素。创建一个节点作为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：

实现说明：此实现为入队和出队方法（offer、poll、remove() 和 add）提供 O(log(n)) 时间；remove(Object) 和 contains(Object) 方法的线性时间；检索方法（peek、元素和大小）的恒定时间。

阅读 API，我猜您可能需要覆盖Comparator<? super E> comparator()，或者至少根据您的需要对其进行修改。那应该这样做。