[leetcode] Find the celebrity

不是最优解法... time O(n^2) space O(n)但能过

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

/* 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) { HashSet<Integer> potential = new HashSet<Integer>(); potential.add(0); for(int i = 0; i < n; i++){ if (potential.contains(i)){ int beKnown = 0; boolean knowOther = false; for (int j = 0; j < n; j++){ boolean iKnowsj = knows(i,j)&&(i!=j); boolean jKnowsi = knows(j,i)&&(i!=j); knowOther |= iKnowsj; if (iKnowsj && !jKnowsi) potential.add(j); if (!iKnowsj && jKnowsi) beKnown++; } if (knowOther){ potential.remove(i); }else if(beKnown == n-1){ return i; } } } return -1; } }

网上搜了下,可以这么想
（限制只有一个candidate..）
不是candidate的条件是... 它知道someone或者someone不知道你..
只要不满足的就不是candidate..
然后过一次 再验证一下candidate 有效否

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

/* 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) { if (n <= 0) return -1; int candidate = 0; for (int i = 1; i < n; i++){ if (knows(candidate, i)){ candidate = i; } } for (int i = 0; i < n; i++){ if (i != candidate && (!knows(i, candidate) || knows(candidate, i))) return -1; } return candidate; } }