明星问题

题目：有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。

这应该是阿里今年的实习生笔试中的一道题目，看论坛上有人列出来，感觉挺有意思，分析一下。

囧，两个人一组，若同组两个人互相不认识或互相认识，丢掉该组，否则丢掉一组中不被认识的那个人，一轮过后剩下的人数不超过原来的一半，继续此方法，最多n次即可找出

这是某某学弟给出的解法。
简单来说，2个人一组，互相认识需要两次询问，也就是说，一轮过去共需要询问2 * (n/2)次….，因此最终的的复杂度应该为：
n + n/2 + n/4….

不得不说，这是一种很失败的做法，完全把问题复杂化了。
其实解法很简单，假设有1，2，3，4，5个人
从1开始，问1是否认识2
如果认识，留下2，淘汰1
如果不认识，留下1，淘汰2
之后留下的继续询问3…….
最终剩下的那个就是所谓的明星。
这种解法利用的是减小数据规模的思路，不断将问题的解集合缩小，最终得到解。和从n个数中找到出现次数大于n/2的那个问题很类似。

如果仅仅是这样，也没什么好写的，但是，如果这个问题做个变形。
假设这n个人里不止有一个明星，而这些明星之间互相认识（符合常理），但他们都不认识任何群众，该如何找出全部明星？

解法和上面的很类似，任意选择一个人开始，依据上面的算法思路，最终完成时，留下的那个一定是明星。
那么再循环一次，选出所有他认识的，即可…..

如果问题继续复杂化，明星不止一个，同时群众一定认识明星，明星也互相认识，而且明星可能认识群众…..这个就完全和现实情况类似了。
但是这样的话会出现一个悖论，如果一个人被其他所有人认识，那么他是不是明星，只有他自己知道…

网址：明星问题 http://c.mxgxt.com/news/view/243976

相关内容

明星采访问题大全
明星对待感情问题
问题明星的营销攻略
问一些韩国娱乐圈明星的问题 ？
明星怎么成了“问题人群”？
问题明星的四大营销策略
明星版权问题 知乎
明星代言问题食品该担何责？
体育明星访谈主要问题
明星代言企业品牌问题研究

随便看看