# 277.搜寻名人

[原题](https://leetcode-cn.com/problems/find-the-celebrity/)

## 一、模拟

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

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

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

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

```python
# 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)

```python
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，因此效率不如方法一

```python
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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/201-400/277.-sou-xun-ming-ren.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.