LeetCode 277 Find the Celebrity

LeetCode 277 Find the Celebrity

链接：leetcode.com/problems/fi…

方法：贪心

时间复杂度：O(n)，对knows(a,b)的调用最多不会超过3n

空间复杂度：O(n)

想法：这个题就是先初始化一个可能的结果，一开始设res为0，然后一路遍历过去，只要knows(res, i)，说明res认识i，说明res再也不可能是celebrity，那就把res设为i，最后再全扫一边看看res是不是有任何违反celebrity标准的行为。以上是对代码的文字描述，并没有什么卵用，还不如说一说这个题为什么这样做是对的，即，为什么以上述的方式求出可能的结果res，那么res就是所有人里面唯一一个有可能是celebrity的？不会漏掉什么结果吗？

比方说出现knows(res,i)为true的时候，说明res再也不可能是celebrity，因为res认识别人了，这个很好理解。在res和i之间的那些元素，res没有被设成那些，所以说res不认识那些人，所以说那些人不可能是celebrity。所以从res到i，只有i有可能是celebrity。一开始我们将res设为0，可以想象，假设说中间knows(0,3)为true，那说明1和2绝对不是celerity，这时候把res设成3，然后继续跑，然后在某处比方说knows(3,7)为true，说明456全都不是celebrity，设为7......这样模拟会发现这样扫描一遍不会有没有考虑的元素，到最后res是谁，谁就是那个唯一有可能是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 res = 0;
        for (int i = 1; i < n; i++) {
            if (knows(res, i)) {
                res = i;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (res != i && (knows(res, i) || !knows(i, res))) {
                return -1;
            }
        }
        
        return res;
    }
}