leetcode 277. 搜寻名人

发表于 分类于 阅读次数：

解题思路

“名人” 定义：
其他所有 n - 1 个人都认识他/她，而他/她并不认识其他任何人

若a不认识b => b一定不是名人，a可能是名人
若a认识c => a一定不是名人，c可能不是名人

时间复杂度

O(n)

调用 knows 的最大次数为 3 * n

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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:
        candidate = 0

        for i in range(n):
            if knows(candidate, i):
                candidate = i
        
        for i in range(candidate):
            if knows(candidate, i) or not knows(i, candidate):
                return -1
        
        for i in range(candidate+1, n):
            if not knows(i, candidate):
                return -1
        
        return candidate