# 277 Find the Celebrity

input是一個整數n，內建knows(a,b)API，可判斷a是否知道b
celebrity的定義：大家都知道他，但他不知道任何人，
回傳celebrity的編號，若沒有則回傳-1

• idea1:

  1. O(n^2), for everyone, count how many people they know, and how many people know them. The one who knows nobody is a candidate
  2. use n*n matrix, save know relationship, List of candidate

• code:

  /* 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) {
        boolean[][] knowRelationship = new boolean[n][n];
        List<Integer> candidate = new ArrayList<>();
  
        //build know relationship
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i!=j){
                    knowRelationship[i][j] = knows(i,j);
                }else{
                    knowRelationship[i][j] = true;
                }
            }
            if(count == 0){
                candidate.add(i);
            }
        }
  
        //check if everyone knows candidate
        for(int i : candidate){
            boolean isCeleb = true;
            int j=0;
            while(isCeleb && j < n){
                isCeleb = isCeleb && knowRelationship[j][i];
                j++;
            }
            if(j == n && isCeleb) return i;
        }
  
        return -1;
      }
  }
  

此方法顯然不理想，時間和空間都需要O(n^2)。
所以參考了別人提供的解法。

• idea 2: 一開始把candidate設為0，第一個for迴圈找candidate，如果candidate認識i的話，就把candidate換成i（因為candidate不該認識任何人），選好candidate後，進入第二個迴圈，檢查是不是大家都認識candidate。

• psudocode:

  candidate = 0
  for(int i=1 to n)
      if(candidate knows i)
          candidate = i
  
  for(int i=0 to n)
      if( i!=candidate && knows(candidate, i) || !knows(i,candidate) ) return -1
  
  return candidate