JAVA:实现FindTheCelebrity寻找名人问题算法(附完整源码)

最新推荐文章于 2023-10-29 20:54:29 发布

源代码大师

最新推荐文章于 2023-10-29 20:54:29 发布

阅读量917

点赞数

分类专栏： Java算法完整教程文章标签：算法数据结构 java

不予转载，严禁转载，违者必纠。

本文链接：https://blog.csdn.net/it_xiangqiang/article/details/126317025

版权

Java算法完整教程专栏收录该内容

725 篇文章 ¥29.90 ¥99.00

订阅专栏

超级会员免费看

本文详细介绍了如何使用JAVA实现FindTheCelebrity算法，通过数据结构和算法知识，解决名人识别问题。文章包含完整的源代码示例，帮助读者深入理解算法的实现过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

JAVA:实现FindTheCelebrity寻找名人问题算法



public class FindTheCelebrity extends Relation {
   
    public int findCelebrity(int n) {
   
        //initialize candidate to 0
        int candidate &

了解本专栏

订阅专栏解锁全文

超级会员免费看

确定要放弃本次机会？

福利倒计时

: :

立减 ¥

普通VIP年卡可用

立即使用

源代码大师

关注关注

0
点赞
踩
0

收藏

觉得还不错? 一键收藏
0
评论
分享

复制链接

分享到 QQ

分享到新浪微博

扫一扫
打赏
打赏
打赏举报

举报

专栏目录

订阅专栏

寻找名人问题算法的JAVA实现

TechWhizKid的博客

08-14

259

算法的思路是，首先假设第一个人是可能的名人，然后遍历其他人，如果当前人认识第一个人，则第一个人不可能是名人，否则当前人不可能是名人。最后，我们再次遍历所有人，检查是否有人不认识第一个人，如果有则第一个人不是名人，否则第一个人可能是名人。寻找名人问题是一种著名的算法问题，要求在一个人际关系网络中，找到一个特殊的人物，即该人物被其他人认识，但是他却不认识任何其他人。这表示在给定的人际关系网络中，ID为4的人物被其他人认识，但他却不认识任何其他人，所以他是名人。以上就是寻找名人问题的JAVA实现。

归纳法之名人问题

思考使人沉静

07-08

2525

黑土说，什么名人，就是个人名！ 这里的名人，不光是个人名，还是个孤陋寡闻的家伙呢。 名人问题 定义：在所有n个人中，一个被所有其他人知道但却不知道别人的人。 如果存在这样的名人，找出来。 判断张三是否知道李四的唯一办法是提问（查询）张三：“你知道李四吗？”。 这是找有向图G<E, V>中的度为|V|的汇点。如果获得了G的邻接矩阵，那就是查找 出度=0且入度=|V|-1的点 但是获得邻接矩阵的代价太大，因为

参与评论您还未登录，请先登录后发表或查看评论

java名人_识别名人 · Find the Celebrity

weixin_29216353的博客

02-22

380

［抄题］：假设你和n个人在一个聚会中(标记为0到n - 1)，其中可能存在一个名人。名人的定义是所有其他n - 1人都认识他/她，但他/她不知道任何一个。现在你想要找出这个名人是谁或者验证这个名人不存在。你唯一可以做的事情就是提出如下问题：“你好，A，你认识B吗？” 来获取A是否认识B。您需要通过询问尽可能少的问题(以渐近的意义)来找出名人是谁(或验证其不存在)。你得到一个辅助函数...

名人问题 (Celebrity problem)

java开发指南博客【转载】

07-02

1718

问题：在一个房间里有 N 个人，其中一个是名人，所谓名人就是大家都认识他，但是他不认识任何人。其它人可能认识房间里面另外的一部分人。你可以问任何人问题，但是问题只能是：你认识 X 吗，对方回答 Yes or No. 请问最少要问多少个问题才能把名人找出来？分析：我们把人编号，比如从1 到 N。我们考虑最坏情况：你问每一个人是否认识 X ，如果大家都认识，那么 X 一定是名人，如...

名人问题算法时间复杂度

anmoji6472的博客

01-06

1791

这是一道leetcode上面的题目，同时也是Anany的算法书的一道课后题题目贴在这里 Suppose you are at a party withnpeople (labeled from0ton - 1) and among them, there may exist one celebrity. The definition of a celebrity i...

名人问题

qzq2514的博客

02-27

5265

题目: 在一次聚会中，你想找出来聚会的人中所有的名人，名人就是别人认识他，而他不认识别人。现在在聚会的k个人中，输入邻接矩阵adj[i][j]用来表示他们之间的关系，其中 adj[i][j]=1表示i认识j,adj[i][j]=0表示i不认识j。输入: 第一行输入k，表示一共有k个人,编号从1到n 之后k行输入邻接矩阵输出; 输出所有名人

python领域的名人_名人问题算法解析与Python 实现 O(n) 复杂度（以Leetcode 277. Find the Celebrity为例）...

weixin_39984963的博客

11-29

338

1. 题目描述 Problem DescriptionLeetcode 277. Find the CelebritySuppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebri...

名人问题（分类讨论），士兵问题（找规律）

最新发布

zhi6fui的博客

10-29

456

【名人问题】n个人中的名人是指这样一个人:他不认识别人，但是每个人都认识他。设计一个高效算法，找出该名人或者确定这群人中没有名人。因为名人的定义是全部人认识他，他不认识全部人。2. j 认识 i,当 i 不认识 j。1.如果 i 认识别人，或者别人不认识他，那么他不是名人。题干主要意思：一个人被全部人认识，当时他不认识全部人。e[ i ][ j ] = 1,表示i 认识 j。这时有出边的一定不是名人。时间复杂度为：O(n),空间复杂度为:O（名人一定是出度为0 ，入度为 n的。

数据结构查找算法

07-22

整理的数据结构里的各种查找算法，适合面试，考试复习。

leetcode——277.寻找名人

Dedication_的博客

07-05

532

题目有一个名人或者没有名人所有人都认识名人，名人不认识所有人思路代码 bool knows(int a, int b); class Solution { public: int findCelebrity(int n) { int k = 0; //通过所有人认识名人将其放上擂台 for(int i = 1; i < n; i++) k = knows(i, k)?k:i;

277. Find the Celebrity

BigFatSheep的博客

10-14

227

Description Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/...

【名人问题】有 n 个人他们之间是否认识用邻接矩阵表示(1表示认识，0表示不认识)，并且 A 认识 B 并不意味着 B 认识 A，名人定义为他不是认识任何人且所有人都认识他的人。求出所有名人。

Tom里的同学的博客

11-09

1078

n个人中的名人是指这样一个人:他不认识别人，但是每个人都认识他。任务就是找出这样一个名人，但只能通过询问“你认识他/她吗?”这种问是来完成。设计一个高效算法，找出该名人或者确定这群人中没有名人。你的算法在最坏情况下需要问多少个问题?

[LeetCode] 搜寻名人

瞬Future

05-29

703

假设你是一个专业的狗仔，参加了一个n人派对，其中每个人被从0到n - 1标号。在这个派对人群当中可能存在一位“名人”。所谓 “名人” 的定义是：其他所有n - 1个人都认识他/她，而他/她并不认识其他任何人。现在你想要确认这个 “名人” 是谁，或者确定这里没有“名人”。而你唯一能做的就是问诸如 “A你好呀，请问你认不认识B呀？”的问题，以确定 A 是否认识 B。你需要在（渐近意义上）尽可能少的问题内来确定这位 “名人” 是谁（或者确定这里没有 “名人”）。在本题中，你可以使...

【LeetCode - 277】搜寻名人

学哥斌的博客

09-13

895

【中等】数组

名人问题算法解析与Python 实现 O(n) 复杂度（以Leetcode 277. Find the Celebrity为例）...

weixin_30569001的博客

12-14

1000

1. 题目描述 Problem Description Leetcode 277. Find the Celebrity Suppose you are at a party withnpeople (labeled from0ton - 1) and among them, there may exist one celebrity. The definition of a c...

[LeetCode] 277、搜寻名人

aift的专栏

12-06

1496

题目描述假设你是一个专业的狗仔，参加了一个 n 人派对，其中每个人被从 0 到 n - 1 标号。在这个派对人群当中可能存在一位 “名人”。所谓 “名人” 的定义是：其他所有 n - 1 个人都认识他/她，而他/她并不认识其他任何人。现在你想要确认这个 “名人” 是谁，或者确定这里没有 “名人”。而你唯一能做的就是问诸如 “A 你好呀，请问你认不认识 B呀？” 的问题，以确定 A 是否认识 B...

LintCode领扣算法问题答案：645. 识别名人

二当家的白帽子

03-22

307

645. 识别名人描述假设你和 n 个人在一个聚会中(标记为 0 到 n - 1)，其中可能存在一个名人。名人的定义是所有其他 n - 1 人都认识他/她，但他/她不知道任何一个。现在你想要找出这个名人是谁或者验证这个名人不存在。你唯一可以做的事情就是提出如下问题：“你好，A，你认识B吗？” 来获取A是否认识B。您需要通过询问尽可能少的问题(以渐近的意义)来找出名人是谁(或验证其不存在)。你得到一个辅助函数 bool know(a，b)，它会告诉你A是否知道B.实现一个函数 int findCele