277. Find the Celebrity

发表于 | 分类于

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.

解法1: Greedy

这题用暴力法解的话是O(N^2)的复杂度，那么要降低复杂度只有O(N), O(logN), O(NlogN)几种。似乎binary search也不能很好解决。在这种情况下，有一类算法可能有奇效，就是greedy。
可以用greedy的题目有一类特征就是有的时候题目会告诉，如果有的话有且仅有一个解。
这里我们就先遍历一遍数组，找到一个可能为celebrity的数字。
然后再验证一遍该数字，是否满足条件，如果不满足条件，那么就说明没有celebrity。如果有，那么就是他。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution extends Relation {
    public int findCelebrity(int n) {
        int celebrity = 0;
        for (int i = 0; i < n; ++i) {
            if (knows(celebrity, i)) {
                celebrity = i;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (celebrity != i && (knows(celebrity, i) || !knows(i, celebrity))) {
                return -1;
            }
        }
        return celebrity;
    }
}