题目重点：n−1 次比较选唯一可能人选，再验证‘不认识任何人、所有人都认识他’，避免只做排除不做证实。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 n 人编号 0..n-1，`knows(a,b)` 返回 a 是否认识 b；Celebrity c 不认识任何其他人且每个其他人都认识 c。n=0 返回 -1。
- 是否认识自己不影响判定；题目只给题名/原题描述，若真实题目有变体（噪声关系、查询上限），需另核。
解题路线
- 候选从 0 开始与每个人 i 比：若 candidate 认识 i，candidate 不可能是 Celebrity，换 i；否则 i 不可能是 Celebrity，保持 candidate。每次比较淘汰一人，n−1 次后至多一个候选。
- 排除阶段没有证明剩余者真的符合全部关系，必须第二趟验证对每个 i≠c：knows(c,i) 为 false 且 knows(i,c) 为 true。任何一项不符返回 -1。
- 正确性来自每轮在两人中至少排除一人：若 c→i，则 c 出局；否则 i 出局。一个 Celebrity 若存在，不会在这条规则下被排除。
- 若 knows 是昂贵网络 API，可缓存重复关系，统计最多约 3n 次逻辑调用；训练代码不假设 API 可批量。
手动走一遍
三人 A、B、C：A 认识 B，则 A 出局；B 不认识 C，则 C 出局，B 为候选。还需验证 B 不认识 A/C、A/C 都认识 B；若其中一项失败，答案不存在。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def find_celebrity(n: int, knows) -> int:
if n <= 0:
return -1
candidate = 0
for person in range(1, n):
if knows(candidate, person):
candidate = person
for person in range(n):
if person != candidate and (knows(candidate, person) or not knows(person, candidate)):
return -1
return candidate
复杂度
O(N) 次 knows 调用、O(1) 额外空间；验证阶段最多 2(N−1) 次调用，排除阶段 N−1。训练代码 20,000 组随机有向关系矩阵与全枚举 oracle 对照。
易错点与追问
容易失分的边界
- 只完成淘汰阶段就返回 candidate。
- 关系方向写反。
- 把互相认识当 Celebrity 条件。
- n=0 未处理。
- 把两人的相同名字/属性当节点身份。
继续深挖
- knows API 很慢时如何批量/缓存？
- 有少量错误关系时如何找‘近似 Celebrity’？
- 如果只需判断候选是否存在，能否少于线性查询？
- 关系随查询变化时还可证明吗？
