存储标记和学生等级的最佳数据结构

Question

我有相应标记和等级的学生的以下信息

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

学生的等级与学生的分数成反比.我必须找到最佳的数据结构来存储上述信息,以便以最佳方式执行以下操作(最佳时间复杂度).可以假设学生姓名是唯一的.

1. 给出学生姓名,找到分数和等级
2. 给定排名,找到学生的标记和名称
3. 更新学生的标记.

我正在考虑使用两个hashmaps一个用于学生和标记映射,另一个用于学生姓名和排名映射.这有更好的数据结构吗？有没有办法可以利用秩与标记成反比的事实.

Answer 1

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

1. 一个哈希表,从学生的名字映射到他的品位.
2. 学生的订单统计树,其中比较的关键是成绩.

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

1. 找到学生的排名:在哈希映射中找到它,然后在树中找到它的顺序统计(排名).
2. 更新学生成绩:在地图中查找旧成绩,将其从地图和树中删除,然后使用新值重新插入.
3. 给定排名,使用订单统计树查找相关学生及其成绩.

此外,O(1)仅使用哈希映射在(平均情况下)中查找学生成绩.

注意:

您可以将学生姓名 - >成绩图的实现切换为树图而不是哈希图,而不会过多地影响复杂性,并保证更好的最坏情况行为.(通过此更改,找到等级也将是O(logn)而不是O(1).