JavaScript中具有O(n)时间复杂度的朋友推荐算法
JavaScript中具有O(n)时间复杂度的朋友推荐算法
提问于 2022-09-03 11:17:04
const data = [
{
name: 'Bob',
friends: ['Alice', 'Eve', 'Charlie']
},
{
name: 'Alice',
friends: ['Bob', 'Dan']
},
{
name: 'Dan',
friends: ['Alice', 'Eve']
},
{
name: 'Charlie',
friends: ['Bob']
}
];
function get_top_k_recommended_friends(name, cutoff) {
}
get_top_k_recommended_friends('Alice', 2) // [Eve, Charlie]
get_top_k_recommended_friends('Alice', 1) // [Eve]该函数接受两个整数( user_id，cutoff_k)，并向这个特定的user_id提供新朋友(表示为整数列表)的建议。推荐朋友的定义如下：
A recommended friend is a friend who has mutual friends with the original user_id’s friends.
For example, assume Alice is friends with Bob and Bob is friends with Eve but Alice is not friends with Eve. So when you call get_recommended_friends(Alice), you get Eve. You also get Alice if you call get_recommended_friends(Eve).
If Bob also is friends with Charlie but Alice is not friends with Charlie, then calling get_recommended_friends(Alice) should yield [Eve, Charlie].编写get_recommended_friends的两个重要要求是
- 推荐朋友的返回列表必须按照与所请求的用户拥有的最多数量的共同朋友进行排序。
- 他们只应该返回顶部k推荐朋友(k是一个截止)
根据提供的数据，调用get_top_k_recommended_friends(爱丽丝，2)应该产生夏娃，查理在夏娃之前被命令，因为夏娃是艾丽斯的两个朋友(鲍勃和丹)的朋友，查理只是爱丽丝的一个朋友(鲍勃)的朋友。Get_top_k_recommended_friends(爱丽丝，1)将交出夏娃。
回答 1
Stack Overflow用户
发布于 2022-09-05 02:43:55
图中与根(原始用户)的距离为2并连接到至少一个距离为1的节点的节点应该是相互的朋友。
(例如夏娃和查理与爱丽丝的距离是2，两者都与距离1的节点相连(鲍勃和丹))
因此，对于距离2 (f2)的每个朋友，您可以计算它连接到的距离1的节点数(mutual_count)。
get_top_k_recommended_friends(user, cutoff)
for f1 in friends[user]:
for f2 in friends[f1] - friends[user]: // friends of f1 but not of user
for f3 in friends[f2]: // check each edge(f2, f3)
if edge(f2, f3) not visited && f3 != f1 && f3 in friends[user]:
// f2 is a mutual friend of f1 and f3
// f1 and f3 are both friends of user, so f2 is a recommended friend
mutual_count[f2] += 1
mark edge(f2, f3) and edge(f3, f2) as visited
return k_largest(mutual_count, cutoff)在O(1)中可以检查集合中是否存在元素。该算法只访问根的距离1和2的朋友(以及它们的边)，所以在return k_largest(mutual_count, cutoff)之前的所有内容都应该是O(n+m)，其中n和m分别是上述节点和边的数目。
对于k_largest，您可以使用快速选择算法找到kth的最大值，然后筛选出k个最大值并对其排序，其平均复杂度为O(n +k log k)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/73591812
复制相关文章
相似问题
腾讯云开发者
