277._Find_the_Celebrity.md

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