存储学生分数和排名的最佳数据结构

Question

我有以下相应分数和排名的学生信息

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

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

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

我正在考虑使用两个哈希图，一个用于学生和分数映射，另一个用于学生姓名和排名映射。有更好的数据结构吗？有什么办法可以利用排名与分数成反比的事实吗

Answer 1

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

一个哈希映射，将学生姓名映射到他的成绩。
order statistic tree 的学生，比较的关键是成绩。

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

找一个学生的rank：在hash map中找，然后在tree中找它的order statistic(rank)。
更新学生成绩：在地图中找到他的旧成绩，将其从地图和树中删除，然后使用新值重新插入。
给定排名，使用顺序统计树查找相关学生及其成绩。

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

注：

您可以将学生姓名-> 成绩图的实现切换为树图而不是散列图，而不会过多影响复杂性，并保证更好的最坏情况行为。（通过此更改，查找成绩也将是 O(logn) 而不是 O(1)。

Answer 2

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

快速阅读byStudent
更新速度较慢 O(n)。如果更新比较多，可以考虑把reorder从addOrUpdate方法中拉出来，分批更新，每批后从外面调用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;
    }
}

存储学生分数和排名的最佳数据结构

Best Data Structure to store marks and ranks of students

java

algorithm

time-complexity

data-structures