众里寻他千百度：名流问题 :: labuladong的算法小抄

[labuladong]

文章链接点这里：众里寻他千百度：名流问题

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

打卡打卡

[mengfanxiao777]

当cand和other互相认识的时候不是可以全部排除吗？这样可能if代码多一些，但是速度更快呀。

[cakipaul]

第一次便利可以只调用一次 knows ，不需要调用两次：

    public int findCelebrity(int n) {
        int curr = 0;
        for(int i = 1; i<n; i++) if(knows(curr, i)) curr = i;
        for(int i=0;i<n;i++)
            if(i!=curr&&(knows(curr,i)||!knows(i,curr))) return -1;
        return curr;
    }

[quanweiliu]

暴力求解法是不是有点问题，最后一个判断，我怎么跑的不对，感觉应当放到第二层循环里面

[kosplay]

暴力解法每次拿到know(candidate, other)却只用来判断candiate是否满足一定条件，以后还会在判断other的合法性时再次多触发一次，理论效率至少低一倍。
这类算法优化点在于充分理解名人的定义，运用排除法大幅度减少需要查询的范围，与快排/二分法等优化算法异曲同工，🐂🍺

[zhongweiLeex]

关于文中笔误的问题
在第一幅图 与 第二幅图中间的一段表述中 ， 误将 邻接矩阵 写成了 邻接表

对于名人问题，显然会经常需要判断两个人之间是否认识，也就是两个节点是否相邻，所以我们可以用邻接表来表示人和人之间的社交关系。

[labuladong]

@zhongweiLeex 感谢指出，已修复~

[linyanm]

文章中的题目要会员才能做，有个相同的题目不用会员也可以做，第997题【找到小镇的法官】

不过我感觉这类型的题目用出度和入度计算会比较简单一点，入度等于n - 1，并且出度等于0的节点就是所求的点了

[chengrenfeng]

两人互不认识，都不是名人。只排除一个人而不是两个人，是为了让代码更具有统一性吧。

[deepbreath373]

check in

[dadasdsads]

暴力解法中

for (int cand = 0; cand < n; cand++) {
int other;
for (other = 0; other < n; other++) {

other 如何都会小于n 啊 怎么会满足判断条件 if (other == n) 的 ？

[yonggui-yan]

有趣的排除法！