潜在朋友计数题：用数组统计实现O(N)解法，告别暴力双循环

带新人做算法热身的时候，我特别喜欢拿一些“标题看着云里雾里，套上场景就能吓住人”的题来当切入点。某算法平台上编号 3404 的“谁是你的潜在朋友”就是其中之一。很多人看到“潜在朋友”这四个字，第一反应是“这是不是要建图？是不是要算社交网络？”，等读完题目才发现，它就是一道非常朴素的计数题。系统里有若干读者，每人报出一本自己喜欢的书，你要作为图书管理员回答：和某个人喜欢同一本书的其他人一共有几个，如果没有，就输出“BeiJu”。

这道题特别适合两类人：一类是刚学完数组和循环、想找一道综合题检验自己的新手；另一类是准备带队刷题、想找一个低门槛但能讲出底层通用思路的老手。它考察的东西非常老实：你读题能不能把“潜在朋友”的定义翻译成“同一本书的人数减一”，你能不能把散落在每个人身上的信息重新整理成“以书为维度的统计表”。这两个动作做顺了，这道题就通了。

1. 题目场景与核心考点拆解

1.1 把题目翻译成人话

我先把题目场景复述一遍，因为这步比大多数人想象的重要。

某图书馆系统里有 N 个读者，有 M 本书，一个读者只能选一本自己最喜欢的书，并报出这本书的编号。现在规定：如果有两个读者喜欢同一本书，那他们互为“潜在朋友”。你要输出每个人的潜在朋友数量，如果某个人和其他所有人喜欢的书都不相同，那他就没有潜在朋友，此时输出一个固定的字符串“BeiJu”。

看完这个描述，有个数学关系要想清楚：某个人潜在朋友的数量，并不是“全馆总人数减一”，而是“喜欢这本书的总人数减一”。原因很简单——统计喜欢同一本书的人数时，把读者自己也算进去了，但自己显然不能当自己的朋友，所以要减掉。这个“减 1”就是第一道坎。

1.2 一道看起来像图论、实际上靠计数的题

为什么说这道题容易劝退新人？因为“朋友”这个词很有欺骗性。一些人条件反射地开始构思图算法：读者是节点，喜欢同一本书就连一条边，然后数每个节点的邻居数量。这个思路理论上没错，但完全没必要。

一个读者潜在朋友的集合，本质上就是“喜欢同一本书的其他人”。只要把读者按书编号分组，同一组里除了自己之外都可以当朋友。这跟图论、跟传递关系都没关系，也不用关心“朋友的朋友”是不是朋友。所以它的本质是：给一堆带标签的数据做分组统计，然后根据每组的数量算出每个人的答案。

这道题真正考察的考点有两个：

• 读题翻译能力：能不能从“潜在朋友”自然语言描述里，提炼出“cnt[书编号] - 1”这个精确公式。
• 循环和数组的熟练度：一次循环做统计，再一次循环做推导输出，两次循环配合一个计数数组就能搞定全部。

很多 OJ 入门题不会明着告诉你“请你写一个计数排序”或者“请你用桶的思想”，而是包装成一个生活场景。能不能剥掉外壳看到内核，就是这类题存在的意义。

1.3 这个题适合谁来练

新手可以把它当作“数组下标即值域”的第一课，比背概念有用得多。有经验的选手也可以拿它给新人讲例题，因为它能把一个完整的问题解决流程压缩在半小时内：读题、暴力、优化、编码、调试、扩展。

就算你已经刷了几百道题，我也建议你用一分钟在脑子里过一遍思路，再打开编辑器写一次。这种看似简单的题，很多时候会因为“想当然”而出错。

2. 从暴力双循环到计数数组

2.1 先看暴力解法能走多远

如果没有学过任何数据结构，最直接的想法是这样：

• 对每一个读者 i，遍历所有读者 j。
• 如果 i 和 j 不是同一个人，且他们喜欢的书编号相同，就累加一次。
• 累加结果就是第 i 个读者的潜在朋友数。

对应成伪代码：

code复制for i = 1 to N:
    friends = 0
    for j = 1 to N:
        if i != j and book[i] == book[j]:
            friends += 1
    if friends > 0:
        print(friends)
    else:
        print("BeiJu")

这个写法的正确性毫无疑问，问题出在效率。两层循环的时间复杂度是 O(N²)。如果 N 是 1000，没问题；如果 N 是 10 万，就是 100 亿次比较；如果 N 是 100 万，那就是 1 万亿次比较，评测机跑完等于看了一场长电影。

多数入门题的数据范围不会特别夸张，但你要养成的习惯是：数据范围决定算法选型。哪怕这道题 N 只有几千，写暴力也能过，我还是建议你掌握计数写法。因为同样的思路，稍微变一变数据范围，就是另一道题的解法。

2.2 计数数组：空间换时间的经典一刀

让我用一个生活场景来引入计数数组。

假设你是一个班级的班主任，想知道每个学生有多少个同月出生的同学。最笨的办法是挨个问两两之间生日是否同月；聪明的办法是先在黑板上写 12 个月份，让每个学生在自己生日对应的月份下面画一道正字，最后看每个人所在月份的记录，再减掉自己。

这个“黑板上画正字”的过程，就是计数数组。书的编号从 1 到 M，我们可以开一个长度为 M+1 的数组 cnt，cnt[x] 表示喜欢编号为 x 的书的人数。第一次循环，读入第 i 个人的书编号 book[i]，顺手执行 cnt[book[i]] += 1。全部读完后，cnt 数组里就是每本书的热度。

第二次循环，回到每个人身上。第 i 个人喜欢的那本书编号是 book[i]，喜欢这本书的总人数是 cnt[book[i]]，去掉他自己，潜在朋友数量就是 cnt[book[i]] - 1。如果这个值大于 0，输出它；否则输出 BeiJu。

时间复杂度从 O(N²) 降到了 O(N)，额外加一次对 cnt 数组的初始化，总复杂度是 O(N+M)。空间上多开一个长度为 M+1 的数组，在 M 百万级别以内完全不是问题。

2.3 为什么这里选数组而不是哈希表

写代码的时候有人会问：能不能用哈希表代替数组？答案是能，而且用哈希表会更通用。但这道题提供的是连续的书籍编号，编号范围就是 1 到 M，我们可以直接用一个普通数组按下标访问，速度更快、代码更短，也没有哈希冲突的顾虑。

什么时候适合用哈希表？当“书籍编号”变成“书籍 ISBN 字符串”，或者编号非常稀疏、范围达到 10 亿时，开大数组就不现实了。笔试面试的时候，把两种选择的边界说清楚，会比单纯背出一种写法更有说服力。

我用这张表帮你梳理一下选择依据：

3. 完整代码与提交要点

3.1 一份带注释的 C++ 参考代码

这道题并发数据范围一般不大，下面这份代码可以直接交：

cpp复制#include <iostream>
using namespace std;

const int MAXN = 1005;   // 读者人数上限，按题目范围调整
const int MAXM = 1005;   // 书籍编号上限，按题目范围调整

int book[MAXN];          // book[i] 表示第 i 个人喜欢的书编号
int cnt[MAXM];           // cnt[x] 表示喜欢编号为 x 的书的人数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> book[i];
        cnt[book[i]]++;          // 读完一个读者，就顺手把对应书的人数加一
    }

    for (int i = 1; i <= n; i++) {
        int friends = cnt[book[i]] - 1;   // 去掉自己
        if (friends > 0) {
            cout << friends << '\n';
        } else {
            cout << "BeiJu" << '\n';
        }
    }
    return 0;
}

两个容易忽略的小地方：第一，数组下标从 1 开始，所以 cnt 至少开到 m+1，保险起见开到 MAXM；第二，建议把输出缓冲处理一下，离线和在线评测都对，只是统一用 '\n' 可以让性能更稳。

3.2 Python 版本怎么写得干脆

Python 的话，读入方式要注意一下，因为题目给的是多行输入：

python复制n, m = map(int, input().split())
book = [0] + list(map(int, input().split()))
cnt = [0] * (m + 1)

for b in book[1:]:
    cnt[b] += 1

for b in book[1:]:
    friends = cnt[b] - 1
    print(friends if friends > 0 else "BeiJu")

这个写法完全模拟 C++ 的 1-indexed 风格。不过要提醒一句：如果题目里的 N 比较大，input().split() 一次性读入所有书编号是可行的，但如果出题人把每个读者的书编号分散在多行，你需要写一个循环读取，不能想当然认为所有数字都在同一行。正确做法是逐行读：

python复制n, m = map(int, input().split())
book = [0]
cnt = [0] * (m + 1)
for _ in range(n):
    b = int(input())
    book.append(b)
    cnt[b] += 1

3.3 提交前最容易翻车的三个地方

第一，数组越界。如果 m 等于 1000，而 cnt 数组只开了 1000，访问 cnt[1000] 就会越界。加上对下标不太敏感的新手很容易在这里栽跟头。建议统一开成 MAXM，多 5 到 10 个容量不会错。

第二，字符串拼写。题目要求输出的“BeiJu”不是“Beiju”，也不是“BeiJu”之外的任何变体。输出大小写、字母顺序差一个，评测就是 Wrong Answer，而且这种错误肉眼很难发现。我见过有人在这个字符串上卡了半天，最后对着原文一个个字母核对才找到问题。

第三，多组数据问题。这道题通常是一组输入，但如果你在别的练习题里看到类似“多组测试数据，读到 EOF 结束”，记得把 cnt 数组每次清零。用 fill(cnt, cnt + MAXM, 0) 或 cnt = [0] * (m + 1) 都行，别让上一次的数据残留影响下一组答案。

4. 踩坑记录与调试方法

4.1 新手高频翻车点

我结合带人时看到的真实错误，整理了一张问题对照表：

这里我想单独展开第一行。很多同学不是不会写 cnt - 1，而是压根没意识到“潜在朋友”的定义里必须排除自己。这个坑不是语法问题，是读题问题。所以我在带队时会要求新人把题面的自然语言，先手写成一个数学表达式，写出来是 f[i] = cnt[book[i]] - 1，再写代码，这样正确率立刻上来了。

4.2 拿一个小样例走一遍，比盲目提交有用

我建议任何题到手之后，先用笔推一个覆盖率高的样例。比如用：

code复制3 2
1
2
1

三个人，两本书。第一个人喜欢书 1，第二个人喜欢书 2，第三个人喜欢书 1。先统计，cnt[1] = 2，cnt[2] = 1。然后逐个人算：

• 第 1 个人：cnt[1] - 1 = 1，输出 1
• 第 2 个人：cnt[2] - 1 = 0，输出 BeiJu
• 第 3 个人：cnt[1] - 1 = 1，输出 1

这个样例同时覆盖了“有朋友”和“没朋友”两条路径，推完再提交，信心会足很多。

4.3 定时调试法：把中间结果打出来

如果你写完代码发现答案不对，先别急着一行行读代码。可以在统计结束之后，临时加一句输出，把 cnt 数组打出来。

比如这个人的书编号是 [1, 2, 1]，理论上 cnt[1]=2, cnt[2]=1。如果打印出来不对，说明读入或者统计那一段出问题了。如果 cnt 对，但答案错，问题基本出在后半段的推导逻辑上。

这种“分段验证”的思路适用于所有算法题。很多看起来玄乎的 Bug，本质上是因为你把“输入读取”“统计处理”“输出推导”三个环节混在一起，一错就连环错。拆开验证，任何一个环节都能快速定位。

5. 一个计数思路吃透三种变体

5.1 变体一：统计最受欢迎的书

把题目改一下：不问每个人的潜在朋友，而是问哪本书最受欢迎。这时候只需要一个取 max 的过程：

python复制best_book = max(range(1, m + 1), key=lambda x: cnt[x])
print(best_book)

或者用 C++ 扫一遍 cnt 数组。思路一模一样，连统计部分都不用改。这是在告诉读者：同一个统计表，可以服务多种查询问题。

5.2 变体二：每个人喜欢多本书时怎么去重

如果题目改成“每个人能报多本喜欢的书”，但潜在朋友的定义仍然是“喜欢同一本书的人”，这时要注意一个细节：同一个人如果在一本书上重复出现，只能计一次。

处理方式不复杂：读入时维护一个二维标记数组，或者用集合记录每个人已经喜欢过的书。逐个人处理时，把这个人喜欢的书先放入一个临时集合去重，然后再对去重后的书列表执行 cnt[book]++。去重是关键，否则一个人喜欢一本书三次，会给这本书虚假增加三个人次。

这道题本身不涉及多本书，但面试和竞赛中这套“先去重再统计”的套路经常出现，值得提前熟悉。

5.3 变体三：读者动态加入，实时维护热度榜

如果数据不是一次性给完，而是读者一个个入场，题目要求实时输出当前热度最高的书编号，那光靠这道题的基础写法就不够了。cnt 数组仍然用于计数，但“实时最大值”最好用堆或者有序容器维护。每当一个读者加入，cnt[书] 变大，就更新堆中的信息。

这个变体和原题的关系，就像是“静态统计”和“动态维护”之间的分水岭。但无论怎么变，核心还是那件事：你需要一个以书为维度的计数器。很多复杂系统，包括搜索引擎的词频统计、电商平台的商品热度统计，底层逻辑都长得差不多。

我在实际带新人时特别喜欢用这道题做第一课：先让所有人写暴力解法，然后让每个人亲口说出“暴力慢在哪里”，再引导他们自己想到“能不能用一本书的编号当桶，把读者装进去”。等他们敲出第一版计数代码并成功提交，那种成就感，比直接给他们抄一份正确答案要强烈得多。你也别嫌这题简单，能把简单题做扎实，后面复杂的哈希、桶排序、离线查询才不会虚。