1. 题目描述 Problem Description
2. 题目解析（参考了Prof. Sarrafzadeh 180讲的内容）
首先题目定义了：如果一个人A是名人，那么其他的n-1个人都认识A，而且A不认识其他的n-1个人。这题的目标是要从n个人中找出其中的名人，如果没有，则告知其中没有名人。我们可以调用knows(a,b)函数来询问a是否认识b，而我们要尽量少调用这个函数。
这题的关键是理解题意，题意其实比较容易理解错，所以有几个小问题可以帮大家理解：
（1）n个人中最多可以有几个名人？
答案：是1个。如果这n个人中有2个名人分别为A和B，那么按照定义，如果一个人A是名人，那么其他的n-1个人都认识A，而且A不认识其他的n-1个人，这也就是说A不认识B。但与此同时我们又定义了如果一个人B是名人，那么其他的n-1个人都认识B，那么A也应该认识B。这就产生了 contradiction了。因此其中不可以有2个或2个以上的名人。
(2) 如果其他n-1个人都认识A，但是A认识了n-1个人中其中一个人，那么A还是名人吗？
答案：不是的。
(3) 如果A不认识其他的n-1个人，但是n-1个人中有人不认识A，那么A还是名人吗？
答案：不是的。
-
这题最直接的想法应该是暴力，但是暴力的复杂度是多少呢？对于每个人我们需要询问:
(1) 他是否认识剩下的n-1个人： 最坏的情况需要调用knows(a,b)函数n-1次
(2) 剩下的n-1个人是否认识他：最坏的情况需要调用knows(a,b)函数n-1次
有的可能会重复，但是总体来说需要询问的次数是$\frac{n(n-1)}{2}$。即时间复杂度为 O($n^2$)
-
有没有办法优化算法？
如果我们从n个人中任意挑两个人a,b出来，询问啊是否认识b，那么只有两种情况：
（1）a认识b：那么a肯定不是名人。
（2）b认识a：那么b肯定不是名人。
所以任何一种情况，我们都可以排除掉2个人中的1一个人。如果我们不断地重复的这个过程，直到只剩下一个人，那么我们会做n-1次对比。而剩下这个人是唯一可能成为名人的人，那么我们需要询问剩下的n-1个人是否认识他，也需要询问他是否认识剩下的n-1个人。
因此我们一共需要询问3(n-1)次——时间复杂度为O($n$)。
3. Python 实现
# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):
class Solution(object):
def findCelebrity(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return -1
curr_stay = 0
for i in range(1, n):
if knows(curr_stay, i):
curr_stay = i
for i in range(0, n):
if i == curr_stay:
continue
if knows(curr_stay, i):
return -1
if not knows(i, curr_stay):
return -1
return curr_stay