java - 在用户社交网络中找到前 k 个喜欢

Question

不是家庭作业问题或类似的问题。所以，这是简单的问题陈述: 你有一群用户 U₁, U₂, ..., U_n。 每个用户都有一组 friend ，这是整个用户集中的一个子集。 U₁ -> U₂, U₅, U₈, ..., U_k

同样，U₂ 可能有 friend U₁，U₁₁，...，U_k2。现在有一堆“喜欢”的实体 L₁, L₂, L₃, ... 很明显，每个用户都喜欢子集的对象。所以U₁-> L₁, L₂, L₅, L₁₀>, ... U₂ -> L₄, L₈, L₁₀, ...

现在的问题是，给定一个像上面这样的网络，给定一个用户 ID，我们需要返回 HIS 网络中最喜欢的人以及喜欢它的几个 friend ( friend 可以没有特定的顺序)。

我的想法: 一种想法是维护用户及其 friend 的 HashMap 。这是全局性的。

用户-好友 HashMap

|用户 | friend 和他们喜欢的 map |

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

总的来说，从数据结构的角度来看，我们正在研究全局 HashMap 、每个用户最大堆、每个用户不相交集。

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

Answer 1

Now per user, we will also maintain a max heap of his likes sorted by their frequency within his network.

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

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

然后，当您收到有关用户 ID 的查询时:

1. 制作 HashMap 。
2. 对于用户拥有的每一个点赞，插入 HashMap 中:L_i -> count_i(从 1 开始)。
3. 对于每个 friend ，重复步骤 2。如果 hashmap 中已经存在一个赞，则增加其计数。
4. 在您的 HashMap 中找到前 k 计数。
5. 返回第4步的结果，并销毁count hashmap。