最好的数据结构来存储学生的成绩和等级

Question

我有以下学生的信息，并有相应的分数和等级

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

学生的排名与学生的分数成反比。我必须找到最佳的数据结构来存储上述信息，以便以最优的方式(最佳时间复杂度)执行以下操作。可以假定学生的名字是独一无二的。

1. 给出学生的名字，找到分数和排名
2. 给定的排名，找到分数和学生的名字
3. 更新学生的分数。

我正在考虑使用两个散列映射，一个用于学生和标记映射，另一个用于学生姓名和等级映射。有更好的数据结构吗？有什么办法能让我利用排名与分数成反比的事实吗？

Answer 1

这可以通过两种数据结构来完成：

1. 一个散列映射，从学生的名字映射到他的年级。
2. 一个学生的顺序统计树，其中比较的关键是分数。

这允许您在O(logn)中执行以下所有操作

1. 查找学生的排名:在散列图中找到它，然后在树中找到它的顺序统计量(排名)。
2. 更新学生成绩:在地图中找到他的旧成绩，从地图和树中删除它，然后用新的值重新插入它。
3. 给定一个等级，使用顺序统计树找到相关的学生和他的成绩。

此外，在O(1) (平均案例)中，仅使用散列图就可以找到学生的成绩。

注意：

您可以将学生名->年级图的实现转换为树映射，而不是散列图，而不会对复杂性造成太大影响，并保证更好的最坏情况行为。(发现职系亦为O(logn)，而非O(1)。)

Answer 2

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

• 快速读取byStudent
• 较慢更新O(n)。如果经常更新，可以考虑将reorder从addOrUpdate方法中提取出来，分批更新，并在每个批处理之后从外部调用重新排序。
• 最终快速读取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;
    }
}