Skip to content

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




回到顶部