Ac solution code


  • 1

    Special thanks to @czonzhu

    The basic idea are as the following two steps:

    1. As the celebrity knows no one else, switch the candidate if candidate knows i
    2. Validate the candidate with: 1) !knows(candidate, i); 2) knows(i, candidate)
    

    Time complexity = O(n)

    public int findCelebrity(int n) { 
        int candidate = 0; 
        for (int i = 1; i < n; i++) {// As the celebrity knows no one else, switch the candidate if candidate knows i
             if (knows(candidate, i))  
                 candidate = i;
        }           
        for (int i = 0; i < n; i++) {// Validate the candidate with: 1) !knows(candidate, i); 2) knows(i, candidate)
             if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) 
                 return -1;                  
        }
        return candidate;
     }
    

Log in to reply
 

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