Java AC Solution, first find only possible celebrity then check.


  • 0
    C
    public int findCelebrity(int n) {
        int i=0,j=1;
        //numbers before i all know somebody. i is the number knows nobody after him, so i is the only 'possible celebrity'
        while(j<n){
            if (knows(i,j)) i=j;
            j++;
        }
        //check if i knows nobody and everybody knows i
        for (int p=0;p<n;p++){
            if ( i!=p && (!knows(p,i) || knows(i,p))) return -1;
        }   
        return i;      
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.