“名人”算法的最优解

问题描述 投票：0回答：9

在 

n
人中，“名人”被定义为某人 大家都认识但谁也不认识的人。这 问题是通过询问名人来识别名人（如果存在的话） 仅提出以下形式的问题：“请问，您认识这个人吗？” 在那里？”（假设所有答案都是正确的， 连那个名人也会回答。） 目标是尽量减少问题数量。

这里是否存在阶数小于明显

O(n^2)
的解？

algorithm data-structures time-complexity complexity-theory graph-algorithm
9个回答
17
投票

使用名人问题的分析这里

蛮力解决方案。 该图最多有 

n(n-1)
条边，我们可以通过对每个潜在边提出问题来计算它。在此 点，我们可以通过计算一个顶点来检查它是否是一个汇点 入度及其出度。这个蛮力解决方案要求
n(n-1)
问题。接下来我们展示如何最多使用 
3(n-1)
来做到这一点 问题和线性位置。

一个优雅的解决方案。我们的算法由两个阶段组成：在淘汰阶段，我们淘汰除了一个人之外的所有人。 名人;在验证阶段我们检查这个是否 剩下的人确实是名人。消除阶段 维护一个可能的名人列表。最初它包含所有

n
人们。在每次迭代中，我们从列表中删除一个人。我们 利用以下关键观察：如果人
1
认识人
2
， 那么
1
这个人就不是名人；如果人
1
不认识人
2
， 那么
2
这个人就不是名人。因此，通过询问人
1
是否知道 person 
2
，我们可以从列表中删除 person 
1
或 person 
2
可能的名人。我们可以反复使用这个想法来消除 除了一个人之外的所有人，说人
p
。我们现在通过暴力验证 
p
是否是名人：对于每个其他人
i
，我们都会询问人
p
他是否认识人
i
，我们询问人
i
是否认识 人
p
。如果某人 
p
总是回答“否”，而其他人总是回答“否” 回答是，我们宣布人
p
为名人。否则，我们 断定这个群体中没有名人。

10
投票

  1. 将所有人分成两两。

  2. 对于每一对（A，B），询问 A 是否认识 B。

    • 如果答案是肯定的，A不可能是名人，抛弃他。
    • 如果答案是否定的，B不可能是名人，抛弃他。

    现在只剩下一半人了。

  3. 从 1 开始重复，直到只剩下一个人。

成本O(N)。

8
投票

这是O(N)时间的算法

  1. 将所有元素压入堆栈。
  2. 删除顶部两个元素（例如 A 和 B），如果 B 知道 A 并且 A 不知道 B，则保留 A。
  3. 删除A、B 双方都认识或者都不认识
6
投票

这个问题可以使用图（入度和出度概念）以O(N^2)时间复杂度来解决。

我们还可以使用简单的两指针概念在 O(N) 时间和 O(1) 空间中解决这个问题。 我们将同时比较两个人，一个从头开始，另一个从最后开始，我们会将那个人从不可能是名人的考虑中删除。例如，如果有两个人 X 和 Y，并且 X 可以识别 Y 人，那么 X 肯定不可能是名人，因为它认识该聚会中的某个人。另一种情况是，X 不认识 Y，在这种情况下，Y 不可能是名人，因为聚会中至少有一个人不认识他/她。使用这种直觉两指针概念可以用来找到聚会中的名人。

我在 Youtube 上发现了 algods 制作的一个很好的解释视频。

您可以参考此视频以获得更好的解释。

视频链接：

https://youtu.be/aENYremq77I

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;
}
0
投票

我就是这么做的:)

问题 - 名人的定义是其他人都知道但不认识任何人的人。给定 N 个人（索引为 0...(N-1)），并且定义了一个 KnowOf 函数 如下所示：knowsOf(int person0, int person1) = true 如果人 0 认识人 1，否则为 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;
  }
 }
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;
    }
}
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;
}
0
投票

双指针

 int celebrity(vector<vector<int>>& mat) {
      int n = mat.size();
      
      int p1 = 0;
      int p2 = n - 1;
      
      while (p1 < p2) {
          if (mat[p1][p2] == 1) {
              p1++;
          } else {
              p2--;
          }
      }
      
      int celebrity = p1;
      for (int i = 0; i < n; i++) {
        if (i != celebrity) {
            if (mat[i][celebrity] == 0 || mat[celebrity][i] == 1) {
                return -1;
            }
        }
      }
      
      return celebrity;
  }
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.