java - 用于比较具有最常见属性的项目的高效数据结构

Question

<分区>

Answer 1

听起来你需要Associative Arrays .关联数组将某种类型的键对象映射到另一个可能是不同类型的对象。它通常被称为“ map ”，因为它就是这样做的。 map 可以通过 Hash Table 实现，这意味着您有固定的时间查找您的 key -> 对象映射。对于这个问题，我实际上建议使用 2 个哈希表。第一个将学生姓名映射到所修类(class)列表。第二个将类(class)名称映射到类的学生。您的学生 -> 类(class)查找将非常快，您的类(class) -> 学生列表查找也将很快。此外，当您处理特定学生 X 时，您可以使用第三方将学生姓名映射到一个整数，以计算他们与学生 X 共享一个类(class)的次数。这将是一个非常有效的实现。

最重要的是，它最终可能会非常容易实现。关系映射是如此常见的任务，而关联数组是如此有用，以至于许多语言都内置了它们，或者在标准库中。 Python 有它的字典，Perl 有它的散列，Java 有一个 HashMap(以及许多其他类型的映射)，C++ 有 std::map，尽管它没有散列表支持，也没有恒定的时间访问。除非您被禁止在本练习中使用您的语言标准库，否则您应该不会在运行高效解决方案时遇到太多麻烦。