forked from DengWangBao/Leetcode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFindCelebrity.java
More file actions
28 lines (23 loc) · 635 Bytes
/
FindCelebrity.java
File metadata and controls
28 lines (23 loc) · 635 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 先用排除法扫一轮，剩下的是唯一的候选人，然后再严格判断
*/
public abstract class FindCelebrity {
public int findCelebrity(int n) {
int candidate = 0;
for (int i = 1; i < n; i++) {
if (knows(candidate, i)) {
candidate = i;
}
}
for (int i = 0; i < n; i++) {
if (candidate == i) {
continue;
}
if (knows(candidate, i) || !knows(i, candidate)) {
return -1;
}
}
return candidate;
}
abstract boolean knows(int a, int b);
}