别再一对一去问了：Find the Celebrity 本质是一次“幸存者筛选”

别再一对一去问了：Find the Celebrity 本质是一次“幸存者筛选”

先说一句可能让你恍然大悟的话：

这道题根本不是在“找名人”，而是在“不断排除不可能是名人的人”。

理解了这点，这题就已经解了一半。

一、先把问题说清楚：什么叫“名人”？

我们先别急着写代码，先对齐定义。

在一个有n个人的房间里：

• 名人：

  • 所有人都认识他
  • 他不认识任何人

用逻辑语言翻译一下：

• 对于名人c：

  • knows(i, c) == True，对所有i != c
  • knows(c, i) == False，对所有i != c

注意重点来了👇
👉名人最多只能有一个
👉也可能一个都没有

二、为什么“暴力解法”一看就不对劲？