5 line c++ solution


  • 6
    Y
    int findCelebrity(int n) {
        if(n<2) return n?0:-1;
        int curr = 0, next = 1;
        for(;next<n;next++) if(knows(curr,next)) curr = next;
        for(int i=0; i<n; i++) if(curr != i && (knows(curr, i) || !knows(i, curr))) return -1;
        return curr;
    }

  • 0
    K

    It seems this is O(n)?


  • 0
    Y

    yes, it's O(n)


  • 0
    Z

    Very clear solution!!!So smart.

    I basically share the same idea as yours, but check too many for the potential candidate,so need more n times checking, but I will still share my solution here.

    int findCelebrity(int n) {
        int celebrity=0;
        
        //int count=0;
        for(int b=1;b<n;b++){
            if (celebrity==-1) celebrity=b;
            else if(knows(celebrity,b) && !knows(b,celebrity)) celebrity=b;
            else if(!(knows(celebrity,b) ^ knows(b,celebrity))) celebrity=-1;
            }
         if(celebrity==-1) return -1;
         else for(int i=0;i<n;i++){
             if(i!=celebrity){
                 if( !knows(i,celebrity) || knows(celebrity,i)) return -1;
             }
         }
        return celebrity;
    }

  • 0

    @yu23
    Nice work!


Log in to reply
 

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