名人有关问题的算法

名人问题的算法
问题描述：名人问题
一个名人就是指这样一个人：所有其他人都认识他，并且他不认识任何其他人。现在有一个N个人的集合，以及他们之间的认识关系。求一个算法找出其中的名人（如果有的话）或者判断出没有名人（如果没有的话）。

很著名的一道面试题，希望大家一起讨论一下～～

[解决办法]
建立一个图，A认识B就从A到B划道弧，计算每个节点的入度和出度.入度为N出度为0的即可。
时间复杂度O(N^2)
[解决办法]
间一个图。。遍历， O(n^2)出结果。很直接的想法。
[解决办法]
建立一个结构体数组a[N].count初始值为0,,a[i].count表示第i个人被认识的人数..
a[N].count1初始值为0 ,a[i].count1表示第i个人认识的人数
录入数据,如果k认识i 则a[i].count++;a[k].count1++

录完数据后,遍历数组,如果 a[i].count=N-1 且a[i].count1=0;则是名人
[解决办法]
可以构建一个矩阵，A[N][N]，N是人的个数。
初始化时A[N][N]的值全为0;
每读入一认识关系时，如i认识k,则A[i][k]赋为1；
最后，如果对于一个特定的m，有矩阵A第m行全为0,而第m列全为1,则m为名人。
[解决办法]
这个问题还可以优化
因为如果存在名人，那按定义只可能有一个
剩下的计算，如LS说的，建个有向图
第一次遍历找出是否只存在一个节点，出度为0，如果存在这样的节点，说明可能存在名人，如果不存在，那肯定不存在名人，直接返回就可以
第一次遍历，判断除第一步找的出度为0的点之外，其它的节点是否都存在一条指向出度为0节点的边，如果其它节点都满足，则说明出度为0的点就是名人，否则不存在名人
[解决办法]
只是处理输入，就需要O(E)的时间，其中E是边的数量。
如果有了数据，应该O(n)就可以统计出谁是名人（根据入度和出度），不用n*log(n),
如果用随机化的方法，应该可以以低于O(n)的时间找到名人，
其方法就是类似DFS，随机找到一个人，如果此人是名人，return，如果不是，对此人做标记，
从此人认识的人里随机找1个，如此迭代，应该比逐个判断效率要高一些，但具体平均复杂度是多少，不太好算。

探讨

听说过有种nlgn的算法，不过不知道具体怎么实现……

[解决办法]
对于任意两个人A和B，如果A认识B，则A不可能是名人；如果A不认识B，则B不可能是名人
如此至多做N-1次，每次根据A和B的相互认识关系，都至少可以减少一个人，最后剩下的人即是，如果存在的话
[解决办法]
12L说出了部分答案，因为这样仅仅能够找到候选的名人。
再遍历一次就能找到了。
[解决办法]
第一步：
从第一个人A和第二个人开始B，如果两个人相互认识，显然两个人不会是名人，剔除两个人名人候选人资格；如果两个人互相不认识，显然两个人也不会是名人，剔除两个人名人候选人资格；如果两个人中，一个人认识另一个人，而另一个人不认识他，不是一般性，假设A认识B，但是B不认识A，显然A不可能是名人，剔除A名人候选人资格；然后看第三个人C和B比较，也可以剔除他们之中一个或者两个人名人候选人的资格，以此类推，到最后，可能剩下一个人，或者没有剩下人，如果没有剩下，显然没有名人，如果剩下一个，他就是名人候选人，假设这个人是Z，进行第二步

第二步：
遍历整个集合，看看是不是所有的其他人都认识Z，而且Z都不认识其他们，如果是，Z就是名人，否则就不是名人：即，不存在名人。

尽管12L没有全部说出来，他的想法还是很好的。
[解决办法]
有向图，找出一个没有出度的点

查看更多 下一篇