AC java O(n) time O(1) space solution with detailed explanation


  • 2
    F
    public int findCelebrity(int n) {
        int celebrity = 0, ask = celebrity + 1;
    /*use this loop to get one potential celebrity*/
        while(ask < n){
    /*if a knows b, that means a cannot be a celebrity*/
            if(knows(celebrity,ask)){
                celebrity = ask;
                ask = ask + 1;
            }else{
    /*if a doesn't know b, that means b cannot be a celebrity*/
                ask = ask + 1;
            }
        }
    /*check if the potential celebrity is a "real" celebrity*/
        for(int i = 0; i < n; i++){
            if(i == celebrity) continue;
    /*if there is anyone who doesn't know the celebrity or the celebrity knows someelss, then it cannot be a celebrity*/
            if(!knows(i,celebrity) || knows(celebrity,i)) return -1;
        }
        return celebrity;
    }
    

    }


Log in to reply
 

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