假设你是一个专业的狗仔，参加了一个 n 人派对，其中每个人被从 0 到 n – 1 标号。在这个派对人群当中可能存在一位 “名人”。所谓 “名人” 的定义是：其他所有 n – 1 个人都认识他/她，而他/她并不认识其他任何人。
现在你想要确认这个 “名人” 是谁，或者确定这里没有 “名人”。而你唯一能做的就是问诸如 “A 你好呀，请问你认不认识 B呀？” 的问题，以确定 A 是否认识 B。你需要在（渐近意义上）尽可能少的问题内来确定这位 “名人” 是谁（或者确定这里没有 “名人”）。
在本题中，你可以使用辅助函数 bool knows(a, b) 获取到 A 是否认识 B。请你来实现一个函数 int findCelebrity(n)。
派对最多只会有一个 “名人” 参加。若 “名人” 存在，请返回他/她的编号；若 “名人” 不存在，请返回 -1。
示例 1:
输入: graph = [
[1,1,0],
[0,1,0],
[1,1,1]
]
输出: 1
解析: 有编号分别为 0、1 和 2 的三个人。graph[i][j] = 1 代表编号为 i 的人认识编号为 j 的人，而 graph[i][j] = 0 则代表编号为 i 的人不认识编号为 j 的人。“名人” 是编号 1 的人，因为 0 和 2 均认识他/她，但 1 不认识任何人。
示例 2:
输入: graph = [
[1,0,1],
[1,1,0],
[0,1,1]
]
输出: -1
解析: 没有 “名人”
注意:
该有向图是以邻接矩阵的形式给出的，是一个 n × n 的矩阵， a[i][j] = 1 代表 i 与 j 认识，a[i][j] = 0 则代表 i 与 j 不认识。
请记住，您是无法直接访问邻接矩阵的。
LeetCode题目地址： https://leetcode-cn.com/problems/find-the-celebrity/
题解：# 循序渐进
## 思路
由于我没有会员。 我讲一下思路吧。
首先，我们可以暴力法。 我们问每一个人是否认识其他人，这种做法简单粗暴。时间复杂度为$O(N^2)$
我们考虑优化。 实际上，本题可以抽象为有向无权图图，我们求解的就是图中的某一个节点，这个节点的入度为N-1，出度为0。 这道题特殊的地方在于，我们事先并不知道这个图的边的情况，我们需要借助一个方法`bool knows(a, b) `来探究边的情况。 那么上面暴力法就是全部边都探索出来。 我们回归一下题目：`名人是指他不认识其他人，其他人都认识它的人`。 也就是说：
- 如果`bool knows(a, b) `返回False的时候，那么b一定不可能是名人。(第一条)
- 如果`bool knows(a, b) `返回True的时候，那么a一定不可能是名人。(第二条)
也就是说`我们只需要调用一次know，然后根据返回值走if else即可。`
这样我们的算法可以先循环遍历一次找出潜在的候选人。然后再循环一次看候选人是否符合名人的条件"其他人全部认识他"，如果是则返回，不是则返回-1。
## 伪代码
```python
candidate = people[0]
for p in people[1:]:
if know(candidate, p):
# 命中上面的”第二条“
candidate = p
# else 没必要了多写了，我们不修改condidate罢了
for p in people:
if isMyself(): continue
if not know(p, candidate): return False
return True
```
这种做法的时间复杂度是$O(N)$