277.md

• 1556ms
• 70%

活用任何人都认识名人，但名人不认识任何人这一特性
如果 knows(i,j) 为ture，说明i不可能是名人
如果 knows(i,j) 为false， 说明j不可能是名人
也就说说任意两人相互比较总能淘汰一个人。
这样就可以在线性时间内找到名人，最简单的方法是迭代一遍数组

但是数组中可能不存在名人，因此需要对第一遍的结果result进行校验
校验方法是 判断数组中每个i 如果 know(result, i)或者！know(i,result)则说明result也不是名人，返回-1；

# 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:
        result = 0
        for i in range(1, n):
            if knows(result, i):
                result = i
        for i in range(n):
            if i!=result:
                if knows(result, i) or not knows(i, result):
                    return -1
        return result

改进

• 1356ms
• 92%

class Solution:
    def findCelebrity(self, n: int) -> int:
        result = 0
        for i in range(1, n):
            if knows(result, i):
                result = i
        for i in range(result):
            if knows(result, i) or not knows(i, result):
                return -1
        for i in range(result+1, n):
            if not knows(i, result):
                return -1
        return result