在 n 个人中，一个“名人”被定义为“所有人都认识但他不认识任何人”的人。问题是，通过只询问形式为“对不起，你认识那边的人吗？”的问题来确定名人，如果存在名人的话（假设所有答案都正确，即使名人也会回答）。目标是尽量减少提问次数。
这里是否有小于明显的 O(n^2) 解决方案呢？
这里是否有小于明显的 O(n^2) 解决方案呢？
“名人”算法的最优解决方案
8
- Abhishek Agarwal
6
3这有帮助吗？http://www.geeksforgeeks.org/the-celebrity-problem/ - therealprashant
3我投票关闭此问题，因为以其当前形式，它不是一个关于编程的问题。 - user1864610
除非您进行任何假设或任何概率派生，否则我认为您已经提供了足够的约束条件以使解决方案为n^2。 - Nilay Vishwakarma
是的，它确实可以。谢谢@therealprashant - Abhishek Agarwal
请查看“生日问题”（http://en.wikipedia.org/wiki/Birthday_problem），我认为它与最佳提问数量有关，可以通过将“和你生日相同”改为“你认识这个人吗”的对话形式进行交流。 - Nikos M.
名人问题分析和算法，并且在这里。 - Nikos M.
8个回答
17
使用名人问题的分析 这里
如果人员暴力解法。 图中最多有
n(n-1)条边，我们可以通过询问每条潜在的边来计算它。此时，我们可以通过计算一个顶点的入度和出度来检查它是否是汇点。这种暴力解决方案需要n(n-1)次询问。接下来，我们将展示如何用最多3(n-1)次询问和线性空间来完成此操作。优雅的解决方案。 我们的算法包括两个阶段：在消除阶段，我们消除所有不可能成为名人的人；在验证阶段，我们检查这个剩下的唯一的人是否真的是名人。消除阶段维护一个可能成为名人的列表。最初，它包含所有的
n个人。在每次迭代中，我们从列表中删除一个人。我们利用以下关键观察结果：如果人1认识人2，那么人1不是名人；如果人1不认识人2，那么人2不是名人。因此，通过问人1他是否认识人2，我们可以将可能成为名人的列表中的人缩减到要么是人1，要么是人2中的一个。我们可以反复使用这个想法来消除除了一个人，例如人p之外的所有人。现在，我们通过暴力方法验证是否有一个名人：对于每个其他的人i，我们询问人p是否认识人i，并且我们询问人们i是否认识人p。
p 总是回答“否”，而其他人总是回答“是”，则我们宣布人员 p 为名人。否则，我们得出结论：此组中没有名人。- Nikos M.
10
把所有人分成一对一对的。
对于每一对(A, B)，问A是否认识B。
- 如果答案是“是”，则A不能成为名人，舍弃他。
- 如果答案是“否”，则B不能成为名人，舍弃他。
现在，只剩下一半的人了。
重复第1步，直到只剩下一个人。
时间复杂度为O（N）。
- salva
2
1@NikosM：是的，但由于每次迭代要处理的项目数量减半，因此总成本不是
O(NlogN)，而只是O(N)。 - salva很棒的解决方案！是的，它的时间复杂度为O(N)。 - nagendra547
7
这里是 O(N) 时间复杂度算法
- 将所有元素推入栈中。
- 移除顶部的两个元素（称为 A 和 B），如果 B 知道 A 而且 A 不知道 B，则保留 A。
- 移除 A、B，如果二者均互相认识或者二者均不认识。
- M Sach
5
这个问题可以使用图形（入度和出度概念）在O(N^2)时间复杂度内解决。
我们还可以使用简单的双指针概念在O(N)时间复杂度和O(1)空间内解决这个问题。我们将一次比较两个人，一个从开头开始，另一个从结尾开始，并且会删除不能成为名人的那个人，例如，如果有两个人X和Y，X可以识别人Y，那么X肯定不是名人，因为它认识这个派对中的一个人。另一种情况是X不认识Y，在这种情况下，Y不能成为名人，因为至少有一个人在这个派对中不认识他/她。使用这种直觉，可以应用双指针概念来查找此派对中的名人。
我在algods的Youtube上找到了一段很好的解释视频。
您可以参考此视频以获得更好的解释。
视频链接：
- Vaibhav Varshney
0
这是我做的方式 :)
问题 - 名人被定义为每个人都知道，但却不认识任何人的人。给定N个人（索引为0...(N-1)），以及一个名为knowsOf的函数，其定义如下：如果person0认识person1，则knowsOf(int person0, int person1) = true，否则为false。如果有，请找出N个给定人中的名人。
// 如果没有名人，则返回-1，否则返回人物索引/编号。
public int celeb(int n) {
int probaleCeleb = 0;
for(int i =1 ; i < n; i++) {
if(knowsOf(probaleCeleb , i)) { // true /false
probaleCeleb = i;
}
}
for(int i =0 ; i < n; i++) {
if( i != probaleCeleb &&
(!knowsOf( i , probaleCeleb) || (knowsOf( probaleCeleb , i)) ) {
probaleCeleb = -1;
break;
}
}
return probaleCeleb;
}
}
- Manjeet Rulhania
0
这是我的解决方案。
#include<iostream>
using namespace std;
int main(){
int n;
//number of celebrities
cin>>n;
int a[n][n];
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
cin>>a[i][j];
}
}
int count = 0;
for(int i = 0;i < n;i++){
int pos = 0;
for(int j = 0;j < n;j++){
if(a[i][j] == 0){
count = count + 1;
}
else{
count = 0;
break;
}
}
if(count == n){
pos = i;
cout<<pos;
break;
}
}
return 0;
}
- archana
0
int findCelebrity(int n) {
int i=0;
for(int j=1;j<n;j++){
if(knows(i,j)){
i=j;
}
}
for(int j=0;j<n;j++){
if(j!=i && (knows(i,j)|| !knows(j,i))){
return -1;
}
}
return i;
}
- Saiteja Ramadev
2
知道（knows）是从哪里来的？它是做什么的？另外，对于未来读者来说，提供一些关于你代码的背景信息会很有帮助。 - Kristianne Nerona
1knows(int i, int j) 是一个布尔函数，如果i认识j则返回true，否则返回false。这是问题中已知的信息。在第一个for循环中，如果knows(i,j)为true，则“i”肯定不是名人，所以将i=j，否则继续。在第一个for循环之后，“i”等于可能是名人的人。在第二个for循环中，我们只是确保“i”是否真的是名人。因此，总共我们会问2N-1个问题。 - Saiteja Ramadev
0
public class Solution {
public int findCelebrity(int n) {
if (n <= 1) {
return -1;
}
int left = 0;
int right = n - 1;
// First find the right candidate known by everyone, but doesn't know anyone.
while (left < right) {
if (knows(left, right)) {
left++;
} else {
right--;
}
}
// Validate if the candidate knows none and everyone knows him.
int candidate = right;
for (int i = 0; i < n; i++) {
if (i != candidate && (!knows(i, candidate) || knows(candidate, i))) {
return -1;
}
}
return candidate;
}
}
- user12018926
1
欢迎来到SO，请提供一些代码解释以使其更易理解。 - Saeed Zhiany
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接