"celebrity"算法的最优解

Question

在 n 人中，“名人”被定义为某人 人尽皆知却无人知晓的人。这问题是识别名人，如果有的话，通过询问仅问题形式，“对不起，你认识这个人吗 over there?”（假设所有答案都正确，甚至那个名人也会回答。）目标是尽量减少问题的数量。

这里有比明显O(n^2)阶数少的解吗？

Answer 1

利用名人问题的分析here

Brute-force solution. The graph has at most n(n-1) edges, and we can compute it by asking a question for each potential edge. At this point, we can check whether a vertex is a sink by computing its indegree and its outdegree. This brute-force solution asks n(n-1) questions. Next we show how to to do this with at most 3(n-1) questions and linear place.

An elegant solution. Our algorithm consists of two phases: in the elimination phase, we eliminate all but one person from being the celebrity; in the verification phase we check whether this one remaining person is indeed a celebrity. The elimination phase maintains a list of possible celebrities. Initially it contains all n people. In each iteration, we delete one person from the list. We exploit the following key observation: if person 1 knows person 2, then person 1 is not a celebrity; if person 1 does not know person 2, then person 2 is not a celebrity. Thus, by asking person 1 if he knows person 2, we can eliminate either person 1 or person 2 from the list of possible celebrities. We can use this idea repeatedly to eliminate all people but one, say person p. We now verify by brute force whether p is a celebrity: for every other person i , we ask person p whether he knows person i , and we ask persons i whether they know person p . If person p always answers no, and the other people always answer yes, the we declare person p as the celebrity. Otherwise, we conclude there is no celebrity in this group.

Answer 2

将所有的人分成两对。
对于每一对（A，B），问A是否认识B。
- 如果答案是肯定的，A不能成为名人，舍弃他。
- 如果答案是否定的，B不能成为名人，舍弃他。
现在只剩下一半人了
从1开始重复，直到只剩下一个人。

成本 O(N)。

Answer 3

这里是O(N)时间的算法

将所有元素压入堆栈。
移除前两个元素（比如 A 和 B），如果 B 知道 A 而 A 不知道 B，则保留 A。
去掉A,B是都认识还是不认识

Answer 4

这是我的解决方案。

 #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;
}

Answer 5

我就是这样做的:)

问题 - 名人被定义为其他人都知道但不认识任何人的人。给定 N 个人（索引为 0...(N-1)），并且定义了一个函数 knowsOf 如下： knowsOf(int person0, int person1) = true 如果 person 0 认识 person 1，否则为 false 找出给定的N个人中的名人，如果有的话。

// return -1 如果没有名人否则 return 人 index/number.

    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;
  }
 }

Answer 6

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;
    }
}

Answer 7

这道题可以用图（入度和出度的概念）求解，时间复杂度为O(N^2)

我们还可以使用简单的两指针概念在 O(N) 时间和 O(1) space 中解决此问题。 我们将一次比较两个人，一个从头开始，另一个从最后开始，我们将把那个不能成为名人的人排除在外。例如，如果有两个人 X 和 Y，并且 X 可以识别 Y 人，那么 X 肯定不能是名人，因为它认识这个党内的人。另一种情况是 X 不认识 Y，在这种情况下，Y 不能是名人，因为聚会中至少有一个人不认识 him/her。使用这种直觉两分球的概念可以用来寻找这个派对中的名人。

我在 Youtube 上找到了 algods 的一个很好的解释视频。

你可以参考这个视频以获得更好的解释。

视频Link：

https://youtu.be/aENYremq77I

Answer 8

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;
}

"celebrity"算法的最优解

Optimal solution for the "celebrity" algorithm

algorithm

complexity-theory

time-complexity

graph-algorithm

data-structures