Easy understand C++ solution with explanation


  • 0
    G

    Assume each one is the candidate of the celebrity, then for each person i, we check all other person j, if i knows j or j not know i, means i is not the celebrity, delete its candidacy, then break the loop and check the person i + 1, else mark j is not celebrity cause i not know j or j knows i. After check person i, if i is still candidate, it means i is celebrity.

      class Solution {
        public:
            int findCelebrity(int n) {
                vector<bool> candidate(n, true);
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < n; ++j) {
                        if (candidate[i] && i != j) {
                            if (knows(i, j) || !knows(j, i)) {
                                candidate[i] = false;
                                break;
                            } else {
                                candidate[j] = false;
                            }
                        }
                    }
                    if (candidate[i]) return i;
                }
                return -1;
            }
    };
    

    Then we can try to optimize our code as following:

    class Solution {
    public:
        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) || !knows(j, i))) break;
                }
                if (j == n) return i;
            }
            return -1;
        }
    };

Log in to reply
 

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