名人问题

有 n 个人他们之间是否认识用邻接矩阵表示(1表示认识,0表示不认识),并且 A 认识 B 并不意味着 B 认识 A,名人定义为他不是认识任何人且所有人都认识他的人。求出所有名人。

分析:最多只能有 1 个名人

笨办法,遍历 i,检查每个 j,是否满足 i 不认识 j 且 j 认识 i。复杂度 O(n2)。

O(n)的方法

  • 对于两个人 i 和 j
    • 如果 i 认识 j,那么 i 显然不是名人,删掉 i
    • 如果 i 不认识 j,则 j 显然不是名人,删掉 j
  • 最后剩余一个人,检查她是否是名人

实现 1

  • 用一个数组保存所有没检查人的编号
  • 数组如何删除 a[i]?
    • 不需要保证顺序的时候,只要 a[i] = a[--n] 即可,把最后一个元素移到 i 位置即可。

时间 O(n),空间 O(n)

for (int i = 0; i < n; i++){
    a[i] = i;
}

while (n > 1){
    // 比较的话因为一直在把后面的移过来,所以只要比较前两个元素
    if (known[a[0]][a[1]]){
        a[0] = a[--n];
    }
    else {
        a[1] = a[--n];
    }
}

for (int i = 0; i < n; i++){
    if ((a[0] != i) && (known[a[0]][i] || !known[i][a[0]])){
        return -1;
    }
}
return a[0];

实现 2

一头扫,时间 O(n),空间 O(1)

  • i < j
  • [0...i-1]没有名人
  • [i...j-1]没有名人
  • 如果 i 认识 j,删掉 i
    • i = j, j = j + 1
  • 如果 i 不认识 j,删掉 j
    • j = j + 1
int i = 0, j = 1
for (; j < n; j++){
    if (known[i][j]){
        i = j;
    }
}
for (j = 0; j < n; j++){
    if ((i != j) && (known[i][j] || !known[j][i])){
        return -1;
    }
}
return i;

实现 3

两头扫,时间 O(n),空间 O(1)

  • i = 0, j = n - 1
  • i < j
    • [0...i-1] 没有名人
    • [j+1...n] 没有名人
    • 如果 i 认识 j,删掉 i,即 i++
    • 如果 i 不认识 j,删掉 j,即 j--
int i = 0, j = n - 1;
while (i < j){
    if (known[i][j]){
        i++;
    } else {
        j--;
    }
}
for (j = 0; j < n; j++){
    if ((i != j) && (known[i][j] || !known[j][i])){
        return -1;
    }
}
return i;