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


  • 0

    第一次正向遍历 找出 candidate, 第二次反向遍历找出candidate2, 如果candidate == candidate2,则candidate为合法,否则返回-1

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

Log in to reply
 

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