2 pass, 2(n-1) calls, easy understand solution


  • 0

    do the first loop with increasing order and find candidate1, do the second loop with reverse order and find candidate2, if candidate1 == candidate2,candidate1 is the celebrity ,otherwise return -1

    bool knows(int a, int b); 
    class Solution {
    public:
        int findCelebrity(int n) {
            int candidate1 = 0;
            for (int i = 1; i < n; ++i) {
                if (knows(candidate1, i)) {
                    candidate1 = i;
                }
            }
            int candidate2 = n-1;
            for (int i = n-2; i >=0; --i) {
                if (knows(candidate2, i)) {
                    candidate2 = i;
                }
            }
            return candidate1 == candidate2? candidate1 : -1;
        }
    };

Log in to reply
 

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