博文中会简要介绍Leetcode P0277题目分析及解题思路。

“Find the Celebrity”是一道中等难度的题目，这道题比较有意思，利用到双指针和贪心算法的思想。

Suppose you are at a party with n people (labeled from 0 to n - 1), and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her, but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

如何思考这道题？

从题目中给出的条件，我们不难发现一个规律：如果A认识B，那么显然A不可能是名人，但B有可能是名人；同理，如果A不认识B，则A有可能是名人，但B不可能是名人。从这个规律出发，我们可以知道，对给定的任意两个人调用API来判断，一定能够排除掉一个。

此时我们可以有个基本的贪心思路，即用两个指针p和q，p指向可能是名人的候选者，q按序扫描所有人。每次按序调用API来判断候选者是否认识q指向的人，如果认识，则移动p指向新的候选者；如果不认识则将q指向下一位，每次保留可能是名人的人作为候选者。

基本思路

在扫描过一遍所有人之后，根据贪心算法可以确认，如果存在名人的话，p指向的人一定是唯一的名人候选者。可以通过反证法证明：若在p之后存在另一个候选人s，那么p一定认识s，但由于p不认识其之后的所有人，所以p一定是它之后的所有人中的唯一候选人；同理，若在p之前存在另一个候选人s，那么s一定不认识自己之后的人，但根据我们的算法，s被淘汰肯定是因为认识别人，则矛盾，证毕。

但这样的算法还是不够的。从证明中也不难看出，p虽然不认识它之后的所有人，但并不代表所有人认识p且p不认识其之前的人，所以我们最后还要再扫描一遍所有人来判断p究竟是不是真名人。

以下是Java的题解代码实现。

/* 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, p = 1;
        while (p < n) {
            if (knows(candidate, p)) {
                candidate = p;
            }
            
            p++;
        }
        
        for (p=0; p<n; ++p) {
            if (p != candidate && knows(candidate, p))
                return -1;
            
            if (p != candidate && !knows(p, candidate))
                return -1;
        }
        
        return candidate;
    }
}

以下是C++的题解代码实现。

/* The knows API is defined for you.
      bool knows(int a, int b); */

class Solution {
public:
    int findCelebrity(int n) {
        int candidate = 0, p = 1;
        while (p < n) {
            if (knows(candidate, p)) {
                candidate = p;
            }
            
            p++;
        }
        
        for (p=0; p<n; ++p) {
            if (p != candidate && knows(candidate, p))
                return -1;
            
            if (p != candidate && !knows(p, candidate))
                return -1;
        }
        
        return candidate;
    }
};