[Leetcode] 277. Find the Celebrity

 

这一题有非常naive的做法,就是从0到n - 1都走一遍,每一个数字都和其他数字进行对比。这个做法的复杂度是O(n ^ 2),太直接了,就不写代码了

这题其实最优解为O(n),做法有点类似tournament。就是16强进8强,8强进4强,4强进2强,最后2决1这样,nba季后赛那样。

用一个简单的例子阐述,譬如说现在有8个人,关系图用2d array 表示如下
X  0  1  2  3  4  5  6  7
0  0  0  0  0  0  0  0  0
1  1  0  1  0  1  0  0  1
2  1  1  0  0  1  0  1  1
3  1  1  1  0  0  0  0  1
4  1  1  1  0  0  1  1  1
5  1  0  0  1  0  0  1  1
6  1  0  1  1  0  0  0  1
7  1  0  0  0  1  0  1  0
在这个关系图里面, arr[i][j] == 1的话就表示i认识j, 0的话就表示不认识。arr[i][i]的值是没有意义的,这个表示自己是否认识自己,是0是1都可以。
肉眼可见,在这个数组里,0就是那个celebrity,因为它不认识任何人,但所有人都认识它。但计算机没有肉眼,所以我们要写算法。。。(好冷~)

tournament做法就是这样的,先通过tournament决出唯一的candidate,然后再对这个唯一的candidate做检查。在这个关系数组里,过程如下:

1. 0和1一组,2和3一组,4和5一组,6和7一组
2. 0不认识1,1认识0,0胜出,2不认识3,3认识2,2胜出。4认识5,5不认识4,5胜出。6认识7,7也认识6。于是双方落败。(另一个case是如果双方相互认识那么也是双方落败,但这里没有)
3. 新的比赛分组诞生: 0和2一组,因为6和7双方落败,5在此时自动胜出
4. 0不认识2,但2认识0,所以0胜出。此时剩下唯一分组0和5。
5. 0不认识5,但5认识0,所以0成为了唯一的candidate。
6. 然后我们对0做最后的遍历检测。发现通过。所以0就是答案。

根据上述描述,可以得到代码如下:
 

    public int findCelebrity(int n) {
        if (n == 0) return -1;
        int candidate = tournament(0, n - 1);
        if (candidate == -1) {
            return candidate;
        }

        for (int i = 0; i < n; i++) {
            if (i == candidate) {
                continue;
            } else if (!knows(i, candidate) || knows(candidate, i)) {
                return -1;
            }
        }
        
        return candidate;
    }
    
    public int tournament(int head, int tail) {
        if (head == tail) {
            return head;
        } else {
            int mid = (head + tail) / 2;
            int left = tournament(head, mid);
            int right = tournament(mid + 1, tail);
            if (left == -1 || right == -1) {
                return left == -1 ? right : left;
            } else {
                if (knows(left, right)) {
                    return knows(right, left) ? -1 : right;
                } else {
                    return knows(right, left) ? left : -1;
                }
            }
        }
    }

事实上这题有一个不一样的做法,也是O(n)的。上面那个做法算上callstack空间是O(n)的,但是这一个做法不需要递归,也不需要额外的空间。原理也是很简单的。
同样也是找candidate再验证candidate,但是找candidate的方式完全不同,更加直观。因为celebrity是所有人都认识他,但他不认识任何一个人。所以如果假设0为初始的备选candidate,然后for (int i = 1; i < n; i++)这样loop下去,遇到第一个备选candidate认识的,就把备选candidate替换成那个被认识的(因为它破坏了不认识任何人的规则),一个合法的candidate,应该要做到不认识loop之后剩下的所有人,这样loop到最后,你就会产生一个candidate,然后做同样的验证即可。

    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) {
                continue;
            } else if (!knows(i, candidate) || i < candidate && knows(candidate, i)) {
                return -1;
            }
        }
        
        return candidate;
    }

倒数第7行的i < candidate是一个优化,因为i >= candidate的情况第一个loop已经验证过了,而这个题目看得出performance瓶颈在于knows这个函数,所以call的越少越好。。