可以用双指针来做。knows(a, b)如果成立,那么 a 肯定不是,因为 celebrity 不认识任何无名鼠辈;同理!knows(a, b)如果成立,b 肯定不是,因为无名鼠辈们都不认识他。
通过双指针扫一遍以后,大概可以逼近到 left,right 了。然后再扫一遍,用来 check left 到底是不是。
/* 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 left = 0, right = n - 1;
while (left < right) {
if (knows(left, right)) {
left++;
} else {
right--;
}
}
for (int i = 0; i < n; i++) {
if (i == left || (knows(i, left) && !knows(left, i))) {
continue;
} else {
return -1;
}
}
return left;
};
}
易错点
check left 到底是不是
if (i == left || (knows(i, left) && !knows(left, i))) {
continue;
} else {
return -1;
}