原题
一、模拟
两人之间关系只有四种：你认识我我不认识你，我认识你你不认识我，咱俩互相认识，咱两互相不认识。 对于情况一，cand 认识 other，所以 cand 肯定不是名人，排除。因为名人不可能认识别人。
对于情况二，other 认识 cand，所以 other 肯定不是名人，排除。
对于情况三，他俩互相认识，肯定都不是名人，可以随便排除一个。
对于情况四，他俩互不认识，肯定都不是名人，可以随便排除一个。因为名人应该被所有其他人认识。
# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:
class Solution:
def findCelebrity(self, n: int) -> int:
q = []
# 所有人入队
for i in range(n):
q.append(i)
while len(q) >= 2:
cand = q.pop()
other = q.pop()
if knows(cand, other) or not knows(other, cand):
# cand不可能是名人，让other归队
q.append(other)
else:
# other不可能是名人，让cand归队
q.append(cand)
# 只剩最后一个候选人，判断其是否为名人
cand = q.pop()
for i in range(n):
if i == cand: #跳过自身
continue
# 即看是否全部人都认识他，且他不认识任何人。有一个反面则-1
if not (knows(i, cand) and not knows(cand, i)):
return -1
return cand
每轮while排除一个候选人，最坏情况执行n轮，时间复杂度O(n)，空间O(n)。
队列只是用于暂存候选人，每次找两个来比较和淘汰，因此归队的顺序无所谓，插头或插尾都可
改进
不用再两两比较，先假设名人为0，然后与other=1~n-1进行比较判断：1、若cand不是名人，则假设为other；2、若other不是名人，则暂时假设cand为名人，other换下一位。
空间复杂度优化为O(1)
class Solution:
def findCelebrity(self, n: int) -> int:
# 先假设cand是名人
cand = 0
other = 1
while other < n:
if knows(cand, other) or not knows(other, cand):
# cand不可能是名人，排除
# 假设other是名人
cand = other
# else:
# other 不可能是名人，排除
# 什么都不用做，继续假设 cand 是名人
other += 1
# 只剩最后一个候选人，判断其是否为名人
for i in range(n):
if i == cand: #跳过自身
continue
# 即看是否全部人都认识他，且他不认识任何人。有一个反面则-1
if not (knows(i, cand) and not knows(cand, i)):
return -1
return cand
二、图（超时）
i认识j，即knows(i,j)返回true，可以理解为一条i指向j的边，此时i出度加一，j入度加一。遍历所有节点两两knows关系，得到一个有向图，则若存在名人，他的入度为n-1， 出度为0
该方法虽然简单直接，但是调用太多次knows，因此效率不如方法一
class Solution:
def findCelebrity(self, n: int) -> int:
inDeg = [0] * n # 所有节点入度
outDeg = [0] * n # 所有节点出度
for i in range(n):
for j in range(i):
if knows(i, j):
outDeg[i] += 1
inDeg[j] += 1
if knows(j, i):
outDeg[j] += 1
inDeg[i] += 1
for k in range(n):
if inDeg[k] == n-1 and outDeg[k] == 0:
return k
return -1
