277.搜寻名人

原题

一、模拟

两人之间关系只有四种：你认识我我不认识你，我认识你你不认识我，咱俩互相认识，咱两互相不认识。 对于情况一，cand 认识 other，所以 cand 肯定不是名人，排除。因为名人不可能认识别人。

对于情况二，other 认识 cand，所以 other 肯定不是名人，排除。

对于情况三，他俩互相认识，肯定都不是名人，可以随便排除一个。

对于情况四，他俩互不认识，肯定都不是名人，可以随便排除一个。因为名人应该被所有其他人认识。

# 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:
        q = []
        # 所有人入队
        for i in range(n):
            q.append(i)
        while len(q) >= 2:
            cand = q.pop()
            other = q.pop()
            if knows(cand, other) or not knows(other, cand):
                # cand不可能是名人，让other归队
                q.append(other)
            else:
                # other不可能是名人，让cand归队
                q.append(cand)
        # 只剩最后一个候选人，判断其是否为名人
        cand = q.pop()
        for i in range(n):
            if i == cand:   #跳过自身
                continue
            # 即看是否全部人都认识他，且他不认识任何人。有一个反面则-1
            if not (knows(i, cand) and not knows(cand, i)):
                return -1
        return cand

每轮while排除一个候选人，最坏情况执行n轮，时间复杂度O(n)，空间O(n)。

队列只是用于暂存候选人，每次找两个来比较和淘汰，因此归队的顺序无所谓，插头或插尾都可

改进

不用再两两比较，先假设名人为0，然后与other=1~n-1进行比较判断：1、若cand不是名人，则假设为other；2、若other不是名人，则暂时假设cand为名人，other换下一位。

空间复杂度优化为O(1)

class Solution:
    def findCelebrity(self, n: int) -> int:
        # 先假设cand是名人
        cand = 0
        other = 1
        while other < n:
            if knows(cand, other) or not knows(other, cand):
                # cand不可能是名人，排除
                # 假设other是名人
                cand = other
            # else:
                # other 不可能是名人，排除
                # 什么都不用做，继续假设 cand 是名人
            other += 1
        # 只剩最后一个候选人，判断其是否为名人
        for i in range(n):
            if i == cand:   #跳过自身
                continue
            # 即看是否全部人都认识他，且他不认识任何人。有一个反面则-1
            if not (knows(i, cand) and not knows(cand, i)):
                return -1
        return cand

二、图（超时）

i认识j，即knows(i,j)返回true，可以理解为一条i指向j的边，此时i出度加一，j入度加一。遍历所有节点两两knows关系，得到一个有向图，则若存在名人，他的入度为n-1， 出度为0

该方法虽然简单直接，但是调用太多次knows，因此效率不如方法一

class Solution:
    def findCelebrity(self, n: int) -> int:
        inDeg = [0] * n     # 所有节点入度
        outDeg = [0] * n    # 所有节点出度
        for i in range(n):
            for j in range(i):
                if knows(i, j):
                    outDeg[i] += 1
                    inDeg[j] += 1
                if knows(j, i):
                    outDeg[j] += 1
                    inDeg[i] += 1
        for k in range(n):
            if inDeg[k] == n-1 and outDeg[k] == 0:
                return k
        return -1