时间复杂度O(n)的JavaScript好友推荐算法实现需求

需求说明 #

实现一个好友推荐函数get_top_k_recommended_friends(name, cutoff)，满足：

• 输入：目标用户名name、返回结果的最大数量cutoff
• 推荐逻辑：推荐用户需满足是目标用户好友的好友，但尚未与目标用户成为好友
• 排序规则：按与目标用户的共同好友数量从多到少排序
• 时间复杂度要求：O(n)，n为总用户数

示例数据 #

const data = [
  {
    name: 'Bob',
    friends: ['Alice', 'Eve', 'Charlie']
  },
  {
    name: 'Alice',
    friends: ['Bob', 'Dan']
  },
  {
    name: 'Dan',
    friends: ['Alice', 'Eve']
  },
  {
    name: 'Charlie',
    friends: ['Bob']
  }
];

预期输出 #

get_top_k_recommended_friends('Alice', 2) // [Eve, Charlie]
get_top_k_recommended_friends('Alice', 1) // [Eve]

实现思路 #

1. 预处理数据：将用户数组转换为以用户名为键的对象，实现O(1)时间查找用户信息，时间复杂度O(n)
2. 快速判断已好友：将目标用户的好友存入Set，用于O(1)时间排除已好友和目标用户自身
3. 统计共同好友次数：遍历目标用户的每个好友，再遍历该好友的所有好友，统计符合条件的用户出现次数（即共同好友数），时间复杂度O(total_friends)，属于O(n)范畴
4. 线性排序取结果：利用桶排序（基于共同好友数的范围）实现线性时间排序，最后截取前cutoff个结果

代码实现 #

function get_top_k_recommended_friends(name, cutoff) {
  // 1. 转换数据为哈希表，O(n)
  const userMap = {};
  for (const user of data) {
    userMap[user.name] = user;
  }

  const currentUser = userMap[name];
  if (!currentUser) return [];

  // 2. 存储当前用户的好友，O(m) m为当前用户好友数
  const currentFriends = new Set(currentUser.friends);
  currentFriends.add(name); // 排除自己

  // 3. 统计候选用户的共同好友次数，O(total_friends)
  const countMap = {};
  for (const friendName of currentUser.friends) {
    const friend = userMap[friendName];
    if (!friend) continue;
    for (const candidate of friend.friends) {
      if (!currentFriends.has(candidate)) {
        countMap[candidate] = (countMap[candidate] || 0) + 1;
      }
    }
  }

  // 4. 桶排序实现O(n)排序
  // 最大可能的共同好友数是当前用户的好友数
  const maxCount = currentUser.friends.length;
  const buckets = Array.from({ length: maxCount + 1 }, () => []);
  
  for (const [user, count] of Object.entries(countMap)) {
    buckets[count].push(user);
  }

  // 从高到低收集结果
  const result = [];
  for (let i = maxCount; i >= 0 && result.length < cutoff; i--) {
    if (buckets[i].length > 0) {
      result.push(...buckets[i]);
    }
  }

  // 截断到cutoff数量
  return result.slice(0, cutoff);
}

验证结果 #

console.log(get_top_k_recommended_friends('Alice', 2)); // [Eve, Charlie]
console.log(get_top_k_recommended_friends('Alice', 1)); // [Eve]

内容的提问来源于stack exchange，提问作者Matiullah Karimi