题目链接

小红的粉丝数量

题目描述

小红有 个小红书账号，第 个账号都有 个粉丝。同一个粉丝可能关注了小红的多个账号。现在已知每个账号的所有粉丝ID，需要计算小红总共有多少个不同的粉丝。

思路分析

这个问题本质上是一个对多个集合进行并集操作后求基数（元素个数）的问题。我们需要统计所有账号的粉丝ID中，唯一的ID总共有多少个。

处理这类去重统计问题，最直接且高效的数据结构是哈希集合（Hash Set）。在 C++ 中是 std::set 或 std::unordered_set，Java 中是 HashSet，Python 中是 set。

算法步骤如下：

  1. 创建一个空的哈希集合，用于存放所有唯一的粉丝ID。

  2. 读取账号总数 。

  3. 循环 次，对每个账号进行处理：

    a. 读取该账号的粉丝数 。

    b. 读取包含 个粉丝ID的一行字符串，并将其分割。

    c. 将分割后的所有ID更新到哈希集合中。由于集合的特性，如果某个ID已经存在，则不会重复插入。

  4. 当所有账号的粉丝ID都处理完毕后，哈希集合中存储的就是所有不重复的粉丝ID。

  5. 输出该哈希集合的大小（size），即为总粉丝数。

根据用户的偏好，在 C++ 中我们将使用 std::set。

代码

#include <iostream>
#include <string>
#include <set>
#include <vector>

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    set<string> unique_fans;
    
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            string fan_id;
            cin >> fan_id;
            unique_fans.insert(fan_id);
        }
    }
    
    cout << unique_fans.size() << endl;
}

int main() {
    solve();
    return 0;
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        Set<String> uniqueFans = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            int k = sc.nextInt();
            for (int j = 0; j < k; j++) {
                String fanId = sc.next();
                uniqueFans.add(fanId);
            }
        }
        
        System.out.println(uniqueFans.size());
    }
}

def solve():
    n = int(input())
    unique_fans = set()
    for _ in range(n):
        # 读取粉丝数量 k，虽然在此解法中不直接使用，但需要消耗掉这一行输入
        k = int(input())
        # 读取粉丝ID并更新到集合中
        fan_ids = input().split()
        unique_fans.update(fan_ids)
    print(len(unique_fans))

solve()

算法及复杂度

  • 算法：使用哈希集合进行去重统计。

  • 时间复杂度：令 为所有账号的粉丝总数（即所有 的和）， 为粉丝ID的最大长度。

    • 使用哈希集合（如 Java 的 HashSet 或 Python 的 set），哈希和插入的平均时间复杂度为 。总时间复杂度为 。

    • 使用平衡二叉搜索树集合（如 C++ 的 std::set），插入操作的时间复杂度为 ，其中 是当前集合中唯一元素的数量。总时间复杂度约为 ，其中 是最终的唯一粉丝总数。在大多数情况下，这两种实现都足够快。

  • 空间复杂度：，用于存储所有唯一的粉丝ID。