Array - 277 Find the Celebrity

277、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 of 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), your function should minimize the number of calls to knows.

Example

Input:
2 // next n * (n - 1) lines 
0 knows 1
1 does not know 0
Output: 1
Explanation:
Everyone knows 1,and 1 knows no one.

思路：

找名人这道题在leetcode上需要订阅才能看，当然lintCode是免费可以练的。 做这道题暴力解法brute force是可以做到的O(n^2)的时间复杂度，很明显需要优化，突破点就在于knows这个api。每次调用knows(i,j)如果返回false，可以确定，j一定不是名人，返回true就可以确定这个i一定认识j，所以i一定不是名人，这样就一定会有一个人可能是名人。然后再使用第一次遍历获取的这个可能是名人的人去遍历一遍，确定是否是名人。所以就是分为两步: 1、遍历数组，找出可能是名人（candidate） 2、将这个找出可能是名人的竞选名人头衔的candidate遍历数组，确定是否是celebrity

代码：

java:

/* The knows API is defined in the parent class Relation.

      boolean knows(int a, int b); */

public class Solution extends Relation {
    /**
     * @param n a party with n people
     * @return the celebrity's label or -1
     */
    public int findCelebrity(int n) {
        // Write your code here
        if (n < 2) return 0;
        
        // 1. 找出可能是名人的竞选者
        int candidate = 0;
        for (int i = 1; i < n; i++) {
            if (knows(candidate, i)) {
                candidate = i;
            }
        }
        
        //2. 确定这个竞选者是否是名人
        for (int i = 0; i < n; i++) {
            if (candidate == i) {
                continue;
            }
            
            if (knows(candidate, i) || !knows(i, candidate)) {
                return -1;
            }
        }
        
        return candidate;
    }
}