algorithm - 对于这个练习题，使用嵌套哈希表是否有效？

Question

我的任务是为以下问题找到最有效的解决方案:我需要打印出给定年份 (y) 流式传输次数最多的 (k) 部电影 (g)，我可以假设检索当前年份需要 o(1)。这方面的一个例子是:每次流式传输电影时，我都会得到电影的名称和类型。 “2014 年度播放量最高的5 爱情 电影是什么？

返回的答案可能是这样的

• MovieName1(爱情)3409 流
• MovieName2(爱情)4000 流
• MovieName3(爱情)5340 流
• MovieName4(爱情)9000 流
• MovieName5(爱情)10000 流

所以我的想法是使用 3 个嵌套哈希表。

• 其中我使用他们的名字(键)映射到频率(值)
• 其中我使用流派(键)映射到映射(名称，频率)(值)
• 最后一个我使用年份(键)映射到 map (流派， map (名称，频率)(值)

这有什么意义吗……我觉得写这篇文章让我自己很困惑……是否可以只使用一个哈希表，将它们的年份用作键并映射到一个节点链表，其中每个节点都包含电影名称、频率和流派？这样会更有效率吗？

所以如果我想更新 bat 侠的频率我可以只做 map.get(2008) 这会给出链表的头部然后做 while(tmp != null){
if(tmp.name == "黑暗骑士"){
温度.频率++；
}

Answer 1

因此，您考虑使用年份 HashMap 到流派 HashMap 、名称 HashMap 到频率 HashMap 。是否有意义？当然。这是解决问题的好方法吗？很可能不会。正如您所说，也可以使用单一的年份主散列映射到流派-名称-频率元组(或结构，在许多语言中 - 如 C、C++、Java 等)的集合。对于集合，您想到了链表，但您也可以很好地使用向量或其他东西(链表通常是最糟糕的一种数据结构)。但这不会更有效，也不一定是解决问题的更好方法，即使它可能更具可读性和可维护性。

我不会谈论不影响时间复杂度的性能改进，因为您已经在评论中明确表示它适用于只关心时间复杂度的考试(这很可悲，但无论如何)。另外，我假设这是您需要解决的唯一问题。

让我们看看如何改进您的想法。碰巧的是，两种解决方案的混合以及一项改进，在时间复杂度方面提供了最佳解决方案，即 O(k)。首先，请注意每个电影名称仅与一个频率相关联，并且每个频率(可能)仅与一个电影名称相关联。并且由于您想根据频率检索电影名称，因此 HashMap 与名称-频率对的线性集合(例如向量或链表)相比没有任何优势。然后，请注意每年和每种流派都(独立地)与多部电影相关联(每部电影都有名称和频率)。因此 HashMap 在这里占有一席之地:对于给定的年份和给定的类型，类似 HashMap 的结构会在预期的恒定时间内为您提供相关的电影。

结合这两个结果，您会得到一个 HashMap ，其中年份和流派作为键，名称-频率对的集合作为值。一个改进可以在 O(k) 时间复杂度内检索给定年份和流派的 k 流式传输最多的电影是一种排序:如果您的名称-频率对在每个集合中按频率排序，您可以简单地返回第一个(或最后一个，取决于顺序)k 名称。

您可能会觉得奇怪的一个细节是 HashMap 同时使用年份和流派作为键。那是一个实现细节。您可以使用两个嵌套的 HashMap 来实现，一个使用年份作为键，另一个使用流派，或者您可以组合年份和流派并直接使用这些对作为键。散列年份-流派对实际上很简单。