时间戳

首页 > 解决方案 > 使用嵌套哈希表解决这个练习问题是否有效？

algorithm - 使用嵌套哈希表解决这个练习问题是否有效？

问题描述

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

返回的答案可能类似于

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

这有什么意义吗...我想写这个让我自己很困惑.. 是否可以只使用一个哈希表，使用他们的年份作为键并映射到每个节点都包含电影名称的节点链表、频率和流派？这会更有效率吗？

所以如果我想更新蝙蝠侠的频率，我可以做 map.get(2008) 这将给出链表的头部，然后做 while(tmp != null){ if(tmp.name == "the dark knight"){ temp.frequency++; }

标签： algorithmperformancedata-structureshashmaphashtable

解决方案

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

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

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

结合这两个结果，您会得到一个哈希图，其中年份和流派作为键，名称-频率对的集合作为值。可以检索k给定年份和流派的O(k)时间复杂度最高的电影的一个改进是排序：如果您的名称-频率对按每个集合中的频率排序，您可以简单地返回第一个（或最后一个，取决于订单）k名称。

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

推荐阅读