LeetCode 277. 搜寻名人
题目描述
题意分析
有
n个人，编号为0..n-1，只能调用knows(a, b)判断a是否认识b。名人必须不认识任何其他人，同时被所有其他人认识；找不到就返回-1。一个人是否认识自己与判定无关。
解法：候选人淘汰
核心思路
[!blue]
不必逐人检查全部关系，先利用一次询问淘汰一个人。当前候选为
cand，新遇到的人为i：若knows(cand, i)为真，候选认识别人，必定不是名人，改用i；若为假，i至少不被候选认识，也不可能是名人，保留cand。每轮之后，已经扫描的人中，除
cand外都至少有一条关系证明自己不是名人。继续扫描便能把所有可能性缩减到一个候选。真正的名人不认识别人且被所有人认识，不会被任一淘汰规则排除，因此如果名人存在，最后留下的一定是他。但“尚未被淘汰”不等于“所有关系都满足”。再遍历每个
i != cand，同时检查knows(cand, i)为假、knows(i, cand)为真。任一方向失败就返回-1，因为其他人已经全部被淘汰；所有检查通过才返回候选编号。名人最多只有一个：若两个人都是名人，其中一个既要被另一个认识，又要求另一个不认识任何其他人，互相矛盾。因此筛选后只验证一个候选就足够，无需保留候选列表。
解题步骤
- 初始化候选
cand = 0。- 依次访问
1..n-1，候选认识当前人就令cand = i，否则保留候选。- 再扫描所有人，跳过候选本人，验证认识关系的两个方向。
- 任一条件不满足返回
-1，否则返回cand。
代码实现
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)$。筛选调用
n - 1次接口，验证至多调用2(n - 1)次，合计至多3(n - 1)次；短路或提前失败可能减少调用。- 空间复杂度：$O(1)$，一个候选。
关键点总结
[!green]
- 筛选与完整验证承担不同任务。
- 自身关系不属于名人定义，验证应跳过。
- 只有一个人时，两轮循环均无有效比较，直接返回编号 0。
易错点总结
[!yellow]
- 筛选后直接返回，会接受尚未全面验证的候选。
- 验证只检查一个方向，会漏掉另一条件。
- 换人规则反过来，会真正淘汰合法名人。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 997. 找到小镇的法官 | 简单 | 同样找被所有人认识且不认识别人的对象，原题给出完整信任边，本题通过knows查询关系。 |
| 面试题 17.10. 主要元素 | 简单 | 同样先淘汰得到唯一可能候选，再验证是否真的满足条件；淘汰依据分别是认识关系与计数抵消。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！