java - Java中同时存在多个数据结构

Question

我正在使用 Java 实现“提交历史记录”，有以下一些方法:

//查找给定学生的所有提交的最高成绩

public Integer getBestGrade ( String unikey );

//给定学生最近提交的内容

public Submission getSubmissionFinal ( String unikey );

//给定学生在给定时间之前最近提交的内容

public Submission getSubmissionBefore ( String unikey , Date deadline );

//添加一个新的提交(可以假设一个学生的提交有不同的时间)

public Submission add ( String unikey , Date timestamp , Integer grade );

//删除提交(可以假设一个学生的提交时间不同)

public void remove ( Submission submission );

//获取所有成绩最高的学生

public List < String > listTopStudents ();

//获取所有最近提交成绩低于最佳提交成绩的学生

public List < String > listRegressions ();

但是，我需要关心的主要问题是时间复杂度。理想情况下，每种方法都需要优于 O(n)(最后两种方法除外)。例如，当使用双向链表时，插入和删除只需要O(1)，但是搜索需要O(n)。另一方面，当使用B树时，搜索需要O(log n)。那么，我想问的是，是否可以同时使用多个数据结构(最多3个)？另外，哪种数据结构适合每种方法？(我正在考虑 treeMap...)谢谢!

Answer 1

我建议您使用HashMap<String, TreeMap<Date, Submission>>作为您的数据结构。

然后你可以:

1. getBestGrade :在 O(1) 中找到学生的所有提交，然后在 O(N) 中找到最佳提交(您可以通过缓存最佳分数来改进它)。
2. getSubmissionFinal :在 O(1) 中找到学生的所有提交，然后在 O(1) 中找到最后一个
3. getSubmissionBefore :在 O(1) 中找到学生的所有提交，然后在 O(1) 中找到结果
4. add :在 O(1) 中查找或添加学生的提交，然后在 O(log(N)) 中添加提交(如果您实现缓存，则应该在此处更新缓存)
5. remove在 O(1) 中查找或添加学生的提交，然后在 O(log(N)) 中删除提交(如果您实现缓存，则应在此处更新缓存)
6. listTopStudents这里需要遍历所有提交(如果没有在 getBestGrade 中实现缓存)，时间复杂度为 O(N)
7. listRegressions迭代学生并检查条件将为您提供 O(N) 总计(同样，缓存将在这里帮助您)