Leaky Cauldron
0%

Find The Celebrity

Posted on

题目(LeetCode #277)

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 the celebrity, but the celebrity 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 ask questions like: “Hi, A. Do you know B?” to get information about 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) that tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party.

Return the celebrity’s label if there is a celebrity at the party. If there is no celebrity, return -1.

Example 1:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

Example 2:

Input: graph = [[1,0,1],[1,1,0],[0,1,1]]
Output: -1
Explanation: There is no celebrity.

Constraints:

  • n == graph.length == graph[i].length
  • 2 <= n <= 100
  • graph[i][j] is 0 or 1.
  • graph[i][i] == 1

题解

方法一

Celebrity 需要满足两个条件：

  1. 除了他以外的所有人都认识他；
  2. 他不认识其他任何人。

由此可知：

  1. 如果 knows(i, j) 为真，i 不可能是 Celebrity；
  2. 如果 knows(i, j) 为假，j 不可能是 Celebrity。

也就是两个人相比较，总能淘汰掉一个人。逐个遍历，依次将剩下的人与下一个人进行比较，即可得到唯一的可能的 Celebrity。

再从头遍历一遍以确保上述两个条件均满足，若不满足则不存在 Celebrity。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 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 result = 0;
        
        for (int i = 1; i < n; i++) {
            if (knows(result, i)) result = i;
        }
        
        for (int i = 0; i < n; i++) {
            if (i == result) continue;
            if (knows(result, i) || !knows(i, result)) return -1;
        }
        
        return result;
    }
}

参考题解: @Xiwen Yue

方法二

与方法一类似，区别仅在于从两端开始比较，两指针相遇之处即为可能的 Celebrity，后续验证过程相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 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 l = 0, r = n - 1;
        
        while (l != r) {
            if (knows(l, r)) l++;
            else r--;
        }
        
        for (int i = 0; i < n; i++) {
            if (i == l) continue;
            if (knows(l, i) || !knows(i, l)) return -1;
        }
        
        return l;
    }
}