Java DC Solution with Explanation


  • 0
    D

    Hi, the most rated solution is brilliant. But this is a typical kind of divide&conquer problem. Here is my DC solution.

    My general idea is to divide every set of people into 2 and try to "conquer". Let S denote the people set in every division.
    (a) if |S|=1, return the person as candidate
    (b) if |S|=2, return the one that "is known" as candidate, or -1 if they both don't know each other.
    (c) if |S|>2, divide the set into 2. Check whether 2 candidates know each other, return the "known" one or -1 if they don't know each other.
    (d) After all steps of DC, we get the final candidate. To check if it's a real celebrity, traverse to find whether he/she knows anyone.

    public class Solution extends Relation {
        public int findCelebrity(int n) {
            // check if he/she knows nobody
            int cand = find(0, n - 1);
            if (cand == -1) return -1;
            for (int i = 0; i < n; i++) {
                if (i != cand && knows(cand, i)) return -1; 
            }
            return cand;
        }
        
        private int find(int lo, int hi) { // find cele candidate: everybody knows
            if (lo == hi) return lo;
            int mi = (lo + hi) / 2;
            int cand1 = find(lo, mi);
            int cand2 = find(mi + 1, hi);
            if (cand1 == -1 && cand2 == -1) return -1;
            if (cand1 == -1) return cand2;
            if (cand2 == -1) return cand1;
            // if cand1 and cand2 is not -1
            if (knows(cand1, cand2)) {
                return cand2;
            } else {
                return knows(cand2, cand1) ? cand1 : -1;
            }
        }
    }
    

Log in to reply
 

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