> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/find-the-celebrity.md).

# Find the Celebrity

<https://leetcode.com/problems/find-the-celebrity/description/>

> Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.
>
> Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
>
> You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.
>
> Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

## Thoughts

knows(a, b) = true意味着a认识b, a肯定不是名人, b可能是名人, a排除; knows(a,b) = false, 意味着b肯定不是名人, 因为a不认识它, b排除. 因此只要一遍遍历, 每次都能排除一个元素, 剩下的成为候选. 但这么做只能保证排除了的肯定不是名人, 但不能保证最后剩下的candidate一定是名人, 因此还要一次遍历进行验证.

## Code

```
/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int res = 0;
        for (int i = 1; i < n; i++) {
            res = knows(res, i) ? i : res;
        }

        for (int i = 0; i < n; i++) {
            if (i != res && (!knows(i, res) || knows(res, i))) {
                return -1;
            }
        }

        return res;
    }
}
```

## Analysis

时间复杂度O(N).