最佳数据结构来存储学生的成绩和排名

Question

我有以下学生信息，包括对应的分数和排名。

Name   Marks  Rank
 A      30     1
 B      20     2
 C      10     3

学生的排名与学生的分数成反比。我需要找到最佳数据结构来存储上述信息，以便按以下方式执行操作（最佳时间复杂度）。可以假设学生姓名是唯一的。

1. 给定学生姓名，查找分数和排名。 2. 给定排名，查找学生姓名和分数。 3. 更新学生的分数。

我考虑使用两个哈希表，一个用于学生和分数映射，另一个用于学生姓名和排名映射。是否有更好的数据结构？ 是否有办法利用排名与分数成反比这一事实？

- poorvank

---

哈希映射（平均）是O(1)的，所以你无法超越它。然而，它们需要空间。 你可以做的是：创建一个具有姓名、分数（一个或多个）、排名的类。然后为姓名和排名创建两个哈希映射，指向该用户的类。虽然费用高但有效。 - EsseTi

另一个选择是创建一个由姓名和分数组成的Comparable类，使用比较方法自动按排名排序，并使用简单的List存储所有对象。优点：排名更新自动进行，需要更少的空间，代码可能更易于阅读。缺点：比哈希表慢，访问不再是o(1)。 - Joel

为什么不使用一个具有字段“姓名”和“成绩”的“学生类”，通过按“成绩”对学生列表进行反向排序来获得排名？您还可以添加一个属性“排名”，每次对列表进行排序时都会重置。 - tobias_k

基本列表不太适合排序，朋友们。为什么要每次都对列表进行排序，而不是使用最大堆优先队列或类似的东西呢 ;-). - pnadczuk

如果两个学生的分数相同，你如何排名？然后，你如何按排名找到一个学生？ - rompetroll

Answer 1

这可以通过两种数据结构来实现：

1. 一个 哈希表，将学生姓名映射到他的分数。
2. 一个有序统计树，其中比较的关键字是分数。

---

这使得您可以在O(logn)中执行以下所有操作：

1. 查找学生的排名：在哈希映射中查找，然后在树中查找其顺序统计量（排名）。
2. 更新学生成绩：在映射中查找他的旧成绩，从映射和树中删除它，并再次插入新值。
3. 给定排名，使用顺序统计树找到相关学生及其成绩。

此外，仅使用哈希映射即可在O(1)（平均情况）中查找学生的成绩。

---

注意：

您可以将学生姓名-成绩映射的实现切换到树映射而不是哈希映射，而不会对复杂度产生太大影响，并保证更好的最坏情况行为。（使用此更改查找成绩也将是O(logn)，而不是O(1)。）

- amit

Answer 2

我的建议是使用两个HashMap，但其中一个逐渐填充而不是将其排序复杂度添加到更新时间中。这将提供以下属性：

• byStudent的快速读取
• 较慢的O(n)更新。如果您需要经常更新，则可以考虑从addOrUpdate方法中移出reorder，批量更新，并在每个批次之后从外部调用reorder。
• 最终快速的byRank读取。

---

class MyClass {
    Comparator<RankedStudent> comp = Comparator.comparingInt(e -> e.marks);
    private Map<String, RankedStudent> repo = new HashMap<>();
    private Map<Integer, RankedStudent> rankCache = new HashMap<>();

    public RankedStudent getByStudent(String student) {
        return repo.get(student);
    }

    public RankedStudent getByRank(Integer rank) {
        return Optional.ofNullable(rankCache.get(rank)).orElseGet(() -> {
            rankCache.putIfAbsent(rank, repo.values().stream().sorted((s1, s2) -> rank == s1.rank ? 1 : 0)
                    .findFirst().orElse(null));
            return rankCache.get(rank);
        });
    }

    public void addOrUpdate(String student, Integer marks) {
        repo.put(student, new RankedStudent(student, marks, -1));
        reorder();
    }

    public void reorder() {
        final Iterator<RankedStudent> it = repo.values().stream().sorted(comp.reversed()).iterator();
        IntStream.range(0, repo.size()).boxed().forEach(i -> it.next().rank = i + 1);
        rankCache.clear();
    }
}

class RankedStudent {

    public String name;
    public int marks;
    public int rank;

    public RankedStudent(String name, int marks, int rank) {
        this.name = name;
        this.marks = marks;
        this.rank = rank;
    }
}

- rompetroll