algorithm - 为检索数据设计最佳结果的数据结构

Question

最近，我在技术面试所引用的一本书中看到了这个问题。问题是这样的-

您将获得有关已选修某些科目的学生的数据。您需要创建一个数据结构，以便如果我查询某个科目中没有学生或学生没有选修任何科目，那么复杂性应该更低。

例如，学生 P1 修读了 S1、S2 和 S3 科目 - 学生 P2 修读了 S1、S4 科目。当我查询 P1 选修的科目时 - 答案应该是 S1、S2、S3当我问谁参加了 S1 的问题时 - 答案应该是 P1 和 P2

到目前为止我已经尝试过...

最初我开始使用 HashMap 和 LinkedList 的组合来解决问题。但最多我得到的检索是 O(1) 和 O(N) 时间与 O(N) 空间。你认为我能做得更好吗？我也考虑过使用 BST，但效果不佳。

期待有一些有趣的回应!!

Answer 1

这个的组合应该工作:

• 学生到科目列表的 HashMap
• 主题到学生列表的 HashMap

这允许预期 O(1) 检索学生正在学习的科目列表或正在学习科目的学生列表(大概列表结构将存储一个计数以允许O(1) 检索元素的数量。

空间复杂度为O(n)。

如果您只想要计数，您可以考虑用简单的计数替换“学生列表”(甚至可能是“科目列表”)。

如果你想支持删除或存在检查，“科目列表”或“学生列表”不会特别有效。为了高效地做到这一点，您可以将这些列表替换为 HashSet。