C++_With brief explanation


  • 0

    If a knows b, then a will not the celebrity, if a does not know b, then b will not be the celebrity. So we could find one possible person from the n persons.

    Next step is that we check this person does not know anyone else and all of the other n-1 ppl know this person.

    bool knows(int a, int b);
    
    class Solution {
    public:
    int findCelebrity(int n) {
        int t = 0;
        for(int i = 1; i < n; ++i){
            if(knows(t,i)){t = i;}
        }
        
        for(int i = 0; i < n; ++i){
            if(i != t){
                if(!knows(i,t) || knows(t,i)) return -1;
            }
        }
        return t;
    }
    };

Log in to reply
 

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