277 Find the Celebrity
277. Find the Celebrity
题目： https://leetcode.com/problems/find-the-celebrity/
难度 : Medium
思路：
算法考试考过
celebrity 是 每个人都知道他，而他不认识任何别的人。
如果用图来看，那就每个别的人都有箭头指向c，而c没有任何出去的箭头。
O(N^2)的代码还是还是很容易想到的
但是我们可以有提升，那么就是可以check knows(a,b)，如果 a knows b，那么可以排除a是celebrity，否则可以排除b是celebrity.
最后还要确认一遍是否这个是真的celebrity
AC代码
# 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
c = 0
for i in xrange(1,n):
if not knows(i, c):
c = i
for i in range(n):
if c != i:
if not knows(i,c) or knows(c,i):
return -1
return c
