C++ solution (7 lines) , easy understanding with simple explanation


  • 6
    L
       int findCelebrity(int n) {
        for (int i = 0, j = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (i != j && knows(i, j)) break; //if i knows j, i is not celebrity
                if (i != j && !knows(j, i)) break; //if j don't know i, not celebrity
            }
            if (j == n) return i; //i does not know any j , but all j know i
        }
        return -1;
    }

  • 0
    Z

    I think this is a O(n^2) solution, right? will it pass the OJ?


  • 0

    @zhengpenghu
    Yes, I think it is O(n ^ 2), but passed


Log in to reply
 

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