LEETCODE 277. Find the Celebrity 解题思路分析

题目大意:

假设你是一个专业的狗仔,参加了一个 n 人派对,其中每个人被从 0 到 n – 1 标号。在这个派对人群当中可能存在一位 “名人”。所谓 “名人” 的定义是:其他所有 n – 1 个人都认识他/她,而他/她并不认识其他任何人。

现在你想要确认这个 “名人” 是谁,或者确定这里没有 “名人”。而你唯一能做的就是问诸如 “A 你好呀,请问你认不认识 B呀?” 的问题,以确定 A 是否认识 B。你需要在(渐近意义上)尽可能少的问题内来确定这位 “名人” 是谁(或者确定这里没有 “名人”)。

在本题中,你可以使用辅助函数 bool knows(a, b) 获取到 A 是否认识 B。请你来实现一个函数 int findCelebrity(n)。

派对最多只会有一个 “名人” 参加。若 “名人” 存在,请返回他/她的编号;若 “名人” 不存在,请返回 -1。

示例 1:

输入: graph = [
  [1,1,0],
  [0,1,0],
  [1,1,1]
]
输出: 1
解析: 有编号分别为 0、1 和 2 的三个人。graph[i][j] = 1 代表编号为 i 的人认识编号为 j 的人,而 graph[i][j] = 0 则代表编号为 i 的人不认识编号为 j 的人。“名人” 是编号 1 的人,因为 0 和 2 均认识他/她,但 1 不认识任何人。

示例 2:

输入: graph = [
  [1,0,1],
  [1,1,0],
  [0,1,1]
]
输出: -1
解析: 没有 “名人” 

注意:

  • 该有向图是以邻接矩阵的形式给出的,是一个 n × n 的矩阵, a[i][j] = 1 代表 i 与 j 认识,a[i][j] = 0 则代表 i 与 j 不认识。
  • 请记住,您是无法直接访问邻接矩阵的。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=277

解题思路分析:

本题最容易想到的肯定是暴力解,查看每个人是否都不认识其他人,并且其他人都认识他。这样做的时间复杂度会是n的平方,虽然没有测试,但目测会超时。

通过题目给出的 knows(a, b) 方法,我们可以得到以下结论:

  1. 如果a认识b,那么a肯定不是名人,b则有可能是名人
  2. 如果a不认识b,那么b肯定不是名人,a则可能是名人

通过该方法,虽然我们不能确定a和b谁是名人,但一定能确定谁不是名人!利用排除法,将肯定不是名人的剔除出数组,剩下可能的候选人。解题时,我们先设定下标为0的人是名人候选人,然后从下标1开始循环数组,查看候选人是否认识当前人,如果认识,当前人变为候选人,反之候选人不变。然后继续循环,用候选人和下一个人比较,直到循环完整个数组,我们可以得到一位候选人,然后再从0开始循环一遍数组,查看该候选人是否不认识任何人,并且其他人都认识该候选人即可得出答案。

另外,本题还可以优化的一个地方是,在排除候选人时,我们可以利用memo数组记录下当前两个人的认识关系,这样最后在确定候选人是否为名人时,如果memo数组中存在该关系,则不用再次调用 knows 方法。

实现代码:

public int findCelebrity(int n) {
    // 记忆数组
    Boolean[][] memo=new Boolean[n][n];
    // 名人候选人
    int res = 0;
    for(int i=1;i<n;i++){
        // 当前人是否认识候选人
        boolean isKnow = knows(i, res);
        // 如果不是认识,候选人肯定不是名人,将当前人变为候选人
        if(!isKnow) res=i;
        // 将认识关系保存至记忆数组
        memo[i][res]=isKnow;
    }
    // 确认候选人是否是名人
    for(int i=0;i<n;i++){
        if(i==res) continue;
        boolean resKnowI=memo[res][i]!=null?memo[res][i]:knows(res,i);
        boolean iKnowRes=memo[i][res]!=null?memo[i][res]:knows(i,res);
        // 如果候选人认识某个人,或者某人不认识候选人,候选人不是名人
        if(resKnowI || !iKnowRes) return -1;
    }
    return res;
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 97.43% of Java online submissions for Find the Celebrity.

Memory Usage: 54.7 MB, less than 6.25% of Java online submissions for Find the Celebrity.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-277-find-the-celebrity-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

LEETCODE 277. Find the Celebrity 解题思路分析》有2条回应

    发表评论

    您的电子邮箱地址不会被公开。