277. Find the Celebrity

本题不算难，但是其实并不好想到的算法

celebriy：

• 所有人都知道他
• 他不知道任何人

最核心的代码是First Pass:

for (int i = 1; i < n; ++i) {
    if (knows(candidate, i)) {
        // update candidate
        candidate = i;
    }
}

• 如果Candidate不知道别人：
  • 如果candidate是celebrity，那那个别人一定不是celebrity
  • 如果candidate不是celebrity，那那个别人也一定不是celebrity，否则会被认出
• 一旦candidate知道了别人，立刻把潜在的candidate换成这个人，因为原来的candidate已经不符合题意了

只要有celebrity的存在，则他一定就是就是candidate，但是celebrity也可能不存在，所以我们要做二次验证。

• 时间复杂度：
• 空间复杂度:

最终代码如下：

/* 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)) {
        // update candidate
        candidate = i;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (candidate == i) {
        continue;
      }
      if (knows(candidate, i) || !knows(i, candidate)) {
        return -1;
      }
    }
    return candidate;
  }
}