n个人，只有1个人是明星，明星所有人都认识，但明星不认识其他_

牛客788634号

问题转换下，所有人都会至少认识一个人，而明星一个人都不认识。

因此，我们可以线性遍历的方式，每次询问，在这N个人中你认识几个人，当X回答为0时，那X即为明星

如果N 很大，采用大而化小的方法，将n个人划分为n/2段，在将n/2划分为n/4。。。。。。。。。依次类推

发表于 2016-05-12 16:01:02 回复(1)

noble4cc

顺序遍历，两个一组比较，如果a认识b，a肯定不是明星，如果a不认识b，b肯定不是明星，逐渐淘汰，最后剩下的一定是明星

发表于 2015-06-10 12:43:56 回复(0)

wanye_z

推荐回答的很好。

总体思路就是进行遍历。

1、如果n不大，那么我们直接一次遍历，如果a认识b，则a不是明星，可以将a排除；如果a不认识b，那么b不是明星，可以将b排除，这样的效率还是很高的。

2、如果n很大，那我们可以采用分布式的算法，即等分为n分之后进行相同的遍历，然后再归并。这样方法也就是分治算法。

发表于 2017-09-11 10:22:51 回复(0)

陈木木

线性扫描一遍，两两比较，每次比较都会排出一个人：若a认识b，则a一定不是明星；若a不认识b，则b一定不是明星；n很大的情况下可以采用分布式方法，每个机器处理一部分数据，最后每个机器选出一个候选，归并

发表于 2015-05-05 14:35:08 回复(1)

superfang

直接说，谁是命硬请举手不就行了吗，搞这么复杂

发表于 2020-01-09 09:32:10 回复(1)

xmk2222

显然，明星为出度为0的节点，同时因为每个人都认识明星，因此不存在其他出度为0的点，因此只要找到出度为0的点即为明星。

发表于 2019-09-10 22:04:12 回复(0)

Disconnect

首先，线性遍历一遍。取出谁都不认识的人的下标号记录为set。

由于所有人中只有明星是谁都认识，并且他不认识任何人的，

所以，可以线性遍历，将每个人中认识的人从set中剔除掉，

直到set长度为1跳出循环。找到明星为set中保留的最后一个元素。

发表于 2019-04-27 20:48:06 回复(0)

Jack201806131912572

我来贡献一个可能曲解了题意的方法。。。。。

因为所有人都“认识”明星，随意抓出2个人问谁是明星，假设抓出来的这两个人都不是明星，那么他们都会指出谁是明星。

假设抓出来的一个人里有一个是明星，他们会指向两个不同的人是明星，再抓出一个人来问谁是明星就好了。

发表于 2018-10-07 11:34:41 回复(2)

小小娃爱吃甜食

n不大是时，线性扫描一遍；

n很大时，采用分布式扫描，最后将结果归并比较

发表于 2015-07-13 15:30:10 回复(0)

n个人，只有1个人是明星，明星所有人都认识，但明星不认识其他