当前位置: 面试刷题>> 社交网络 (经典算法题500道)


题目描述补充

在社交网络中,用户之间通过关注关系形成了一张复杂的网络图。给定一个用户列表和每对用户之间的关注关系,你的任务是编写一个算法来找出每个用户的所有粉丝(即关注该用户的用户)。为了简化问题,我们假设用户编号是从1开始的连续整数,且关注关系是无向的(即A关注B,则B也是A的粉丝)。但实际上在这个问题中,我们应当考虑关注关系是有向的,即A关注B,则B是A的粉丝,但A不是B的粉丝,除非另有指定。

输入

  • 一个整数N,表示用户的总数。
  • 一个二维数组follows,其中follows[i] = [userA, userB]表示用户userA关注用户userB

输出

  • 一个字典(或类似结构),键为用户编号,值为该用户的所有粉丝的列表。

注意

  • 如果有多个用户关注同一个用户,则该用户的粉丝列表中应包含所有这些用户的编号。
  • 用户编号从1开始,并且连续递增。

示例输入

N = 4
follows = [[1, 2], [2, 3], [3, 4], [4, 1]]

示例输出

{
  1: [4],
  2: [1],
  3: [2],
  4: [3]
}

PHP代码示例

<?php

function findFans($N, $follows) {
    $fans = array_fill(1, $N, []); // 初始化用户及其粉丝列表

    foreach ($follows as $follow) {
        $follower = $follow[0];
        $followee = $follow[1];
        $fans[$followee][] = $follower; // 将关注者添加到被关注者的粉丝列表中
    }

    return $fans;
}

// 示例
$N = 4;
$follows = [[1, 2], [2, 3], [3, 4], [4, 1]];
$result = findFans($N, $follows);
print_r($result);

?>

Python代码示例

def find_fans(N, follows):
    fans = {i: [] for i in range(1, N + 1)}  # 初始化用户及其粉丝字典
    for follower, followee in follows:
        fans[followee].append(follower)  # 将关注者添加到被关注者的粉丝列表中
    return fans

# 示例
N = 4
follows = [[1, 2], [2, 3], [3, 4], [4, 1]]
result = find_fans(N, follows)
print(result)

JavaScript代码示例

function findFans(N, follows) {
    const fans = {};
    for (let i = 1; i <= N; i++) {
        fans[i] = []; // 初始化用户及其粉丝列表
    }

    for (const [follower, followee] of follows) {
        fans[followee].push(follower); // 将关注者添加到被关注者的粉丝列表中
    }

    return fans;
}

// 示例
const N = 4;
const follows = [[1, 2], [2, 3], [3, 4], [4, 1]];
const result = findFans(N, follows);
console.log(result);

码小课提醒: 在码小课网站上,你可以找到更多关于数据结构与算法、编程技巧以及实战项目的分享,帮助你提升编程能力。

推荐面试题