Medium
思路蛮好玩的一道题，特别是一开始初次筛选candidate的过程。我们先initialize candidate = 0, 然后开始遍历到n, 如果candidate knows i, 我们就update candidate 为i. 这样一圈下来，找到的candidate后面index肯定不会是celebrity, 为什么呢？因为有人不认识他们, 违背了celebrity的条件；candidate前面的index也不会是celebrity，因为他们knows somebody才会有可能被update掉，也违背了celebrity的条件.
但是第一圈下来我们没办法保证candidate doesn't know index before it, 或者index after candidate knows candidate因为我们实际上通过第一轮扫描只能确定candidate前面的肯定有knows it的，candidate肯定不认识它后面的.
/* 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 candidate = 0;
for (int i = 1; i < n; i++){
if (knows(candidate, i)){
candidate = i;
}
}
for (int i = 0; i < n; i++){
if (i != candidate && knows(candidate,i) || !knows(i, candidate)){
return -1;
}
}
return candidate;
}
}
