java solution, divide and conqure


  • 0
    2
    /* The knows API is defined in the parent class Relation.
          boolean knows(int a, int b); */
    
    public class Solution extends Relation {
        public int findCelebrity(int n) {
            int c = find(0, n - 1);
            for (int i = 0; i < n; i++) {
                if (i == c) {
                    continue;
                }
                if (knows(c, i) || !knows(i, c)) {
                    return -1;
                }
            }
            return c;
        }
        private int find(int lo, int hi) {
            if (lo == hi) {
                return lo;
            }
            int mid = (lo + hi) / 2;
            int left = find(lo, mid);
            int right = find(mid + 1, hi);
            if (knows(left, right)) {
                return right;
            }
            return left;
        }
    }
    

Log in to reply
 

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