My solution with min `knows` calls.


  • 0
    X

    Two round traversal algorithm, I using S/celebrityNotknow to mark the people that relationship is already clear to minimize the function calls.

    int findCelebrity(int n) {
        if(n == 1) return -1;
        int celebrityNotKnow = 0;
        unordered_set<int> S;
        int celebrity = 0;
        for(int i = 1; i < n; ++i) {
            if(!knows(i, celebrity)) {
                celebrityNotKnow = celebrity;
                celebrity = i;
                S.clear();
            } else {
                S.insert(i);
            }
        }
        for(int i = 0; i < n; ++i) {
            if(i == celebrity) continue;
            if(i != celebrityNotKnow) {
                if(knows(celebrity, i)) return -1;
            }
            if(!S.count(i)) {
                if(!knows(i, celebrity)) return -1;
            }
        }
        return celebrity;
    }

  • 0
    N

    The Set is not necessary just save the next index: - I use check instead of S:

        if (n == 1) return -1;
            //HashSet check = new HashSet();
            int celeb = 0;
            int notKnow = 0;
            int check = 0;
        for (int i = 1; i < n; i++) {
            if (!knows(i, celeb)) {
                notKnow = celeb;
                celeb = i;
                check = i + 1;
            } 
        }
        
        for (int i = 0; i < n; i++) {
            
            if (i == celeb) continue;
            if (i != notKnow) {
                if (knows(celeb, i)) return -1;
            }
            if (i < check) {
                if (!knows(i,celeb)) return -1;
            } 
        }
        
        return celeb;           
        }
    

Log in to reply
 

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