0

不是作业问题或类似的东西。所以，这是一个简单的问题陈述：你有一堆用户 U 1， U 2，...，U n。每个用户都有一组朋友，这是整个用户集的一个子集。U 1 -> U 2 , U 5 , U 8 , ..., U k

类似地，U 2可能有朋友 U 1，U 11，...，U k2。现在有一堆“Like”实体 L 1 , L 2 , L 3 , ... 很明显，每个用户都喜欢 Like 对象的子集。所以 U 1 -> L 1 , L 2 , L 5 , L 10 , ... U 2 -> L 4 , L 8 , L 10 , ...

现在的问题是，给定一个像上面这样的网络，给定一个用户 id，我们需要返回 HIS 网络中的最高赞以及几个喜欢它的朋友（朋友可能没有特定的顺序）。

我的想法：一个想法是维护用户及其朋友的哈希图。这是全球性的。

用户好友HashMap

| 用户 | 朋友的地图和他们的喜好|

现在，每个用户，我们还将维护一个最大的他喜欢的堆，按他们在他的网络中的频率排序。我们需要某种不相交的集合来开始，以及实际的最大堆。当查询进来时，给定一个用户 ID，我们从喜欢堆中检索顶部条目，并且对于每个喜欢，我们检索喜欢它的朋友。

总的来说，从数据结构的角度来看，我们正在查看全局哈希图，每个用户最大堆，每个用户不相交集。

这是解决这个问题的最好方法。我完全迷失了 : ( : ( 建议非常受欢迎。我们可以在这里使用最短路径/bfs/dfs 之类的东西吗？

4

1 回答 1

1

现在，每个用户，我们还将维护一个最大的他喜欢的堆，按他们在他的网络中的频率排序。

为什么？这意味着您不断地为每个人维护您的查询的答案，而不仅仅是您被问到的人。因此，对图表的任何更改现在都变得更加昂贵，因为您必须更新所有这些堆。加上每个节点的内存占用，而不是恒定的，取决于他有多少朋友以及他们有多少喜欢。

只保留您所描述的图表，即只是朋友和喜欢的关系。

然后，当您查询用户 ID 时：

  1. 制作一个哈希图。
  2. 对于用户拥有的每一个赞，插入到 hashmap 中：L i -> count i（从 1 开始）。
  3. 对于每个朋友，重复第 2 步。如果 hashmap 中已经存在点赞，则增加其计数。
  4. 在您的哈希图中查找最高k计数。
  5. 返回第 4 步的结果，并销毁 count hashmap。
于 2013-10-26T07:52:58.787 回答