[LeetCode]Find the Celebrity

这道题第一眼看上去可能没有太明确的思路，一般这种情况我们可以尝试从sub problem开始想。如果只有一个人a的话，a自己就是celebrity。如果再加一个人b，如果b知道a，显然b不可能是celebrity，a仍然有可能是。否则，如果a知道b，那么a肯定不是celebrity，而b有可能是，我们就把b选为可能的候选。同理，加上第三个人c之后我们也可以决定是b仍然可能还是c替换b。那么这样我们可以不断地从n - 1的scale推理到n的scale。最后我们会有一个候选者，其他人都被排除了可能，我们还需要验证这个候选者是不是真正的celebrity，这个步骤线性时间就可以完成。时间复杂度O(n)，常数空间，代码如下：