有效的程序来跟踪电影和搜索频率？
在为考试做准备的过程中，我遇到了这个问题。
一个网站将电影流到客户的电视或其他设备上。电影有多种类型之一，如动作片、戏剧、神秘等等。每部电影都属于一种类型(因此，如果一部电影既是一部动作片，又是一部喜剧，那么它就是一种叫“动作片-喜剧”的类型)。该网站拥有大约1000万用户，以及大约2.5万部电影，但两者都在迅速增长。该网站想要跟踪最受欢迎的电影流。你已经被雇佣为首席工程师来开发一个跟踪程序。 (一)每当一部电影被传送给一个客户时，它的名字(例如：“哈罗德和库马尔:逃离关塔那摩湾”和流派(“喜剧”)被发送到你的程序，以便它可以更新它维护的数据结构。 (假设您的程序可以在O(1)时间内调用适当的Java类来获得当前年份。) (二)此外，每隔一段时间，顾客就会想知道y年中k类最热门的k类电影是什么。(如果y是当前年份，那么会计一直到目前为止。)例如，2010年排名前10位的流媒体喜剧电影是什么？这里k= 10，g=“喜剧日”，y=2010年。此查询被发送到您的程序，该程序应该输出最上面的k个电影名称。 描述用于实现这两个需求的数据结构和算法。对于(i)，分析大O运行时间来更新数据结构，以及(ii)大O运行时间来输出顶级k流电影。
我的想法是创建一个哈希表，在链接列表中的哈希表中将每一部新电影添加到各自的类型中。至于第二部分，我唯一的想法是保持链表排序，但这似乎太昂贵了。还有什么更好的选择呢？
Stack Overflow用户
发布于 2015-12-18 12:13:37
您可以使用一个散列表"HT1“在O(1)中完成这一操作，将从(类型、年份、movie_title)映射到迭代器到链接列表(num_times_streamed，电影标题的哈希表)。您可以使用迭代器查看列表中的下一个元素是否用于一个更大的流计数，如果是，则将电影标题插入其中并从另一个表中删除它(如果该表为空，则可以从列表中删除)，否则，如果现有哈希表没有其他标题，则增加num_times_streamed，否则在列表中插入一个新哈希表并添加标题。必要时更新HT1中迭代器的记录。
注意，如上所述，当num_times_streamed值增加时，列表中的操作将使用结束点或现有的迭代器，步骤不超过一个位置，因此O(1)。
要获得最上面的k标题，您将需要一个哈希表HT2，从{斯科舍，年份}到每个链接列表:只需从列表的末尾迭代，就会遇到一个具有最高流计数的电影或电影的哈希表，然后是次高的哈希表等等。如果今年发生了变化，您可能找不到k条目，请随意处理。如果在查找电影标题时发现在HT1中不存在，那么您将为该类型和今年的HT2添加一个新的列表。
更直观地，在哈希表中使用{ } (无论是映射还是集合)，围绕链接列表使用[ ]，围绕分组结构/元组数据使用( )：
HT2 = { "comedy 2015": [ (1, { "title1", "title2" }),
(2, { "title3" }), <--------\
(4, { "title4" }) ], |
"drama 2012": [ (1, { "title5" }), |
(3, { "title6" }) ], |
... | .
}; | .
| .
HT1 = { "title3", -----------------------------------/ |
"title2", ---------------------------------------/
...
};https://stackoverflow.com/questions/34342277
复制相似问题
腾讯云开发者
