Leetcode: Find the Celebrity

最佳做法：O（N）time， O(1)space

The first pass is to pick out the candidate. If candidate knows i, then switch candidate. The second pass is to check whether the candidate is real.

第一遍做法：

像一个擂台一样，一开始维护两个candidate：A 和 B，维护一个stack, 存储所有变量

if knows(A, B), A一定不是，B可能是，A换人：A = stack.pop()

if !knows(A, B), B一定不是，A可能是, B换人：B = stack.pop()

这个问题取巧在于know(A,B)无论如何会淘汰一个，经过N-1回合，一定只剩最后一个候选人AorB，假定是A

最后再验证一下他是不是就好了，

验证方法：所有除他之外的人E依次上擂，这次每个要比两回合

if knows(A,E), return -1

if !knows(E,A), return -1