假设我们有N个人，并且里面可能有一群名人。
每个人都知道每个名人，每个名人只知道其他每个名人。
如果获得了know x y其中的功能returns true or false，请确定名人组。
这个问题是要确定一群名人，而不是确定人们中唯一的名人，例如http://www.geeksforgeeks.org/the-celebrity-problem/。
使用蛮力很容易。我可以构造N个人的所有可能子序列，并根据条件进行过滤（每个人都知道每个名人，每个名人都只知道其他名人）。
我也知道一定只有一个名人团体或一个。
证明：
假设我们有两个名人组，C1和C2。因为每个人都从C1知道ci，所以每个C2的cj也都知道ci。对称地，每个ci都知道cj；因此，C1和C2实际上属于一个组。因此，我们最多只有一个名人团体或一个。
关于可能的线性算法有什么想法吗？
编辑
可能有一群名人，可能没有。
是的，这可以在O（N）中进行（但请参见下面的第二次编辑）。这是一种算法。
枚举从0到N-1的所有N个人。
int find_a_celebrity()
{
int C = 0; // C is a potential celebrity
for( int i=0 ; i<N ; ++i )
if( !know(i,C) ) // C is not a celebrity nor are all j<i, but i might be.
C = i;
for( int i=0 ; i<N ; ++i ) // Loop a second time to check everyone knows C.
if( !know(i,C) ) return -1;
return C;
}
int C = find_a_celebrity();
如果那样的C==-1话，没有名人。否则，集合{ y | know(C,y) }就是所有名人的集合。总共，这在整个N个人中最多进行了3次迭代，因此这是及时发现的O(N)。
编辑：
// Output the set of celebrities
if( C == -1 ) std::cout << "There are no celebrities.";
else for( int i=0 ; i<N ; ++i ) if( know(C,i) ) std::cout << i << ' ';
std::cout << std::endl;
编辑2：
对于此问题有两种解释：
上面的算法解决了案例＃1。只要我们可以假设至少存在一位名人，这种情况也适用于情况2 。否则，我们将不得不最后验证潜在名人列表是否彼此了解，这需要O(N*M)时间，其中M是潜在名人的数量。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句