LeetCode 277. 搜寻名人
目录
题目描述
题意分析
有
n个人，编号 0 到n-1，其中最多存在一位「名人」：所有其他人都认识他，而他谁也不认识。我们不能直接看到人际关系，只能调用knows(a, b)这个接口逐条询问。要求返回名人的编号，不存在则返回 -1。「只能通过接口提问」是这道题最关键的设定，它把优化目标从「时间复杂度」换成了「提问次数」。题目明确希望调用次数低于 $O(n^2)$，这等价于要求：绝大多数人必须在只被问一两次的情况下就被排除掉。
名人的定义拆开是两条：出度为 0（他不认识任何人）和入度为
n-1（所有人都认识他）。两条都是全称量词，所以只做一遍筛选不足以下结论，必须有一个独立的验证阶段。题目保证名人至多一位。这条唯一性是所有淘汰式解法的合法性来源——如果允许多位，「淘汰掉一个」就未必安全。
边界包括：
n = 1时唯一的人自动满足条件（不认识任何人、也没有别人需要认识他）；完全不存在名人时必须返回 -1；以及被淘汰者恰好就是真名人的假象需要被验证阶段兜住。
解法：候选人淘汰
核心思路
暴力做法是对每个人
i检查它与所有其他人的两个方向关系，共约 $2n(n-1)$ 次提问。正确但太贵，瓶颈在于我们对每个人都做了完整的 $O(n)$ 验证，而实际上只有至多一个人能通过验证，其余n-1个人的验证工作全是浪费。观察点是：一次提问就能淘汰一个人。考察
knows(a, b)的两种结果——如果a认识b，那么a有出边，a一定不是名人；如果a不认识b，那么b缺了a这一条入边，b一定不是名人。无论答案是什么，都必然有一方出局。这是本题从平方级降到线性的全部支点。于是用擂台式扫描：维护一个当前候选
cand，从 0 开始，依次拿它和i = 1, 2, ..., n-1比一次。如果knows(cand, i)为真就换成i当候选，否则保留原候选。第一阶段的不变量是：处理完下标
i之后，编号在[0, i]范围内、且不等于cand的人，都已被证明不是名人。归纳理由正是上面那条「一问淘汰一人」：每一轮被淘汰的要么是旧候选（它认识别人），要么是新来的i（它没被旧候选认识）。因此扫描结束时，若名人存在，他一定就是
cand——因为其余所有人都已被证伪。但反过来不成立：cand只是「唯一没被排除的人」，未必真是名人，它可能只是恰好没被问到关键的那一条关系。所以必须有第二阶段的验证：对每个
i != cand，同时检查knows(cand, i)为假且knows(i, cand)为真。任何一条不满足就说明名人不存在，返回 -1。这一步不能省，因为第一阶段只做了n-1次提问，远不足以覆盖名人定义所需的 $2(n-1)$ 条关系。值得单独点明的是，第二阶段验证
cand之前的那些编号（i < cand）时，knows(cand, i)其实是新信息：第一阶段里cand成为候选之后，就再也没被问过与更早编号的关系了。
解题步骤
- 初始化
cand = 0。之所以可以任取一个人做起点，是因为不变量只保证「被淘汰的确实不是名人」，起点本身是否为名人交给后续流程判定。- 从
i = 1扫到n-1，每轮问一次knows(cand, i)。之所以每轮只问一次而不是两次，是因为一次提问的两种结果已经能各自淘汰一人，多问一次不会多淘汰。- 若
knows(cand, i)为真，令cand = i。之所以敢直接抛弃旧候选，是因为「认识别人」直接违反名人定义中的出度为 0，旧候选被永久证伪。- 若为假，保持
cand不变。之所以此时能淘汰i，是因为cand不认识i，而名人必须被所有人认识，i的入度已经缺了一条。- 第一阶段结束后进入验证循环，对每个
i != cand检查knows(cand, i) || !knows(i, cand)，成立就返回 -1。之所以要用「或」把两个方向都查一遍，是因为名人定义包含两条全称条件，任何一条被破坏都说明整个候选不成立。- 验证时跳过
i == cand。之所以必须跳过，是因为多数判题环境中knows(x, x)未定义或返回 true，拿自己和自己比会误触发返回 -1。- 全部验证通过则返回
cand。以
n = 4，关系为「1、2、3 都认识 0，0 谁也不认识，1 认识 2，2 认识 3」为例走一遍，真名人是 0。第一阶段：
cand = 0。i = 1，问knows(0, 1)，0 不认识任何人，返回假，cand保持 0，同时淘汰了 1。i = 2，问knows(0, 2)，假，淘汰 2。i = 3，问knows(0, 3)，假，淘汰 3。扫描结束cand = 0，共 3 次提问。第二阶段：
i = 0跳过。i = 1，knows(0, 1)为假、knows(1, 0)为真，通过。i = 2、i = 3同理通过。返回 0，正确。再看一个无名人的例子：
n = 2，两人互相认识。第一阶段cand = 0，i = 1时knows(0, 1)为真，cand换成 1。第二阶段i = 0：knows(1, 0)为真，第一个条件立刻成立，返回 -1。正确——两人互相认识时谁都不是名人，说明验证阶段确实兜住了第一阶段留下的假候选。
代码实现
public class Solution extends Relation {
public int findCelebrity(int n) {
int cand = 0;
for (int i = 1; i < n; i++) {
if (knows(cand, i)) {
cand = i;
}
}
for (int i = 0; i < n; i++) {
if (i == cand) {
continue;
}
if (knows(cand, i) || !knows(i, cand)) {
return -1;
}
}
return cand;
}
}
func findCelebrity(n int) int {
cand := 0
for i := 1; i < n; i++ {
if knows(cand, i) {
cand = i
}
}
for i := 0; i < n; i++ {
if i == cand {
continue
}
if knows(cand, i) || !knows(i, cand) {
return -1
}
}
return cand
}
复杂度分析
- 时间复杂度：$O(n)$，提问次数至多 $3(n-1)$ 次。凭据是第一阶段固定
n-1次提问，第二阶段对n-1个人各问两次共 $2(n-1)$ 次，两阶段都是单层循环、无嵌套。- 空间复杂度：$O(1)$，凭据是全程只维护
cand和循环变量两个整数，既没有建邻接矩阵也没有记录任何已问过的结果。
关键点总结
- 交互式题目要把优化目标从「运行时间」改成「提问次数」，判断一个做法好不好，看的是「一次提问能换来多少确定的信息」。
- 本题的核心引理是「一次提问必然淘汰一人」：
knows(a,b)为真淘汰a，为假淘汰b。凡是能找到这种「无论答案如何都有收益」的提问，都能把平方级搜索压成线性。- 「筛选 + 验证」是所有淘汰式算法的固定两段式。筛选阶段只保证「留下的是唯一可能」，不保证「留下的一定对」，所以验证不能省——这一点和摩尔投票法完全同构。
- 题目保证的「至多一位名人」是淘汰合法性的前提，看到唯一性保证要立刻想到能否用淘汰法；反之若允许多个答案，淘汰逻辑通常直接失效。
- 验证阶段必须双向都查，因为名人定义是两条独立的全称条件，只查其中一条会漏掉另一半反例。
- 面试视角：面试官会先让你说出 $O(n^2)$ 的做法，然后问「能不能少问一点」。答题时要显式讲出淘汰引理并证明两种结果各淘汰谁，再强调验证阶段的必要性。常见追问是「为什么第二阶段还要问
knows(cand, i)，第一阶段不是问过了吗」，标准回答是：cand被换成新人之后，它与更早编号之间的关系从未被询问。
易错点总结
- 省掉第二阶段直接返回
cand：用例n = 2且两人互相认识，第一阶段留下 1，直接返回 1，而正确答案是 -1。- 第二阶段只检查
!knows(i, cand)而不检查knows(cand, i)：用例n = 2且两人互相认识，knows(1, 0)为真通过检查，返回 1，漏掉了「候选认识别人」这一半反例。- 第二阶段只检查
knows(cand, i)而不检查knows(i, cand)：用例n = 3，0 谁也不认识、1 认识 0、2 谁也不认识，候选留在 0，knows(0, 1)、knows(0, 2)都为假通过，返回 0，但 2 并不认识 0，正确答案是 -1。- 验证循环里忘记跳过
i == cand：用例任意n >= 1，knows(cand, cand)在多数判题实现里返回 true，第一个条件立刻成立，任何输入都返回 -1。- 第一阶段写成
if (!knows(cand, i)) cand = i;，把换人条件写反：用例n = 3，真名人是 0，第一轮knows(0, 1)为假就把候选换成 1，最终候选是 2，验证不通过返回 -1，漏掉了真名人。- 第一阶段的循环从
i = 0开始：用例任意输入，第一轮就问knows(0, 0)，若接口返回 true 会立刻把候选换成 0 本身，虽不改变值但引入了一次无意义提问，在按提问次数计分的判题下会超限。- 用二维数组把所有
knows(i, j)预先查一遍再判断：用例n = 10^3，提问次数达到 10^6，远超题目允许的线性调用量，即使答案正确也会被判失败。- 第一阶段每轮问两次（同时问
knows(cand, i)和knows(i, cand)）来「顺便验证」：用例任意输入，答案正确但提问次数翻倍到 $2(n-1) + 2(n-1)$，而正确认识是「一次提问已足够淘汰一人」，多问的那次不产生新的淘汰。- 认为第一阶段淘汰的人不需要在第二阶段再检查，只验证
i > cand的部分：用例n = 3，1 认识 2、2 谁也不认识、0 认识 1 和 2，候选最终是 2，只验证i > 2时无人可查直接返回 2，但 0 并不认识 2，正确答案是 -1。n = 1时额外写特判返回 -1：用例n = 1，第一阶段和第二阶段的循环都不执行，正常流程返回 0 才是正确答案，多余的特判反而制造了错误。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 169. 多数元素 | 简单 | 摩尔投票同样是「抵消式淘汰 + 验证」，抵消依据是计数而非提问 |
| 229. 多数元素 II | 中等 | 候选从一个扩到两个，抵消规则变复杂，验证阶段必须查两个候选 |
| 997. 找到小镇的法官 | 简单 | 关系以边表形式直接给出，可用入度出度计数一次性判定，无需淘汰 |
| 136. 只出现一次的数字 | 简单 | 同样靠成对抵消定位唯一元素，抵消手段换成异或且无需验证 |