小红的粉丝数量

[题目链接](https://www.nowcoder.com/practice/8f3d949aab804ae8b281b66f7a298af3)

思路

本题要求统计小红所有账号中不重复的粉丝总数。由于同一个粉丝可能关注了小红的多个账号，直接累加每个账号的粉丝数会导致重复计数。

做法

使用哈希集合（Set）来去重：

创建一个空的集合。
遍历每个账号的所有粉丝 ID，将其插入集合中。集合会自动忽略已存在的元素。
最终集合的大小就是不重复的粉丝总数。

以样例为例，三个账号的粉丝分别是：

账号 1：qcjj, qsmcgogo, ducksajin, acidlemon
账号 2：qionghua, benh, jch, qsmcgogo
账号 3：qcjj, pcmsdodo

其中 qsmcgogo 和 qcjj 各出现了两次，去重后共有 8 个不同的粉丝。

代码

C++
Java

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_set<string> fans;
    while (n--) {
        int k;
        cin >> k;
        while (k--) {
            string id;
            cin >> id;
            fans.insert(id);
        }
    }
    cout << fans.size() << endl;
    return 0;
}

import java.util.*;

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

复杂度分析

设所有账号的粉丝总数为 $N$ ，每个 ID 的平均长度为 $L$ 。

时间复杂度： $O(N \cdot L)$ ，每个粉丝 ID 插入哈希集合的均摊时间为 $O(L)$ （需要计算字符串哈希值）。
空间复杂度： $O(N \cdot L)$ ，哈希集合最多存储 $N$ 个长度为 $L$ 的字符串。