名人问题
有 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;