算法题：名人问题，给出最优解法

Answer 1

参考回答：

问题描述：

有n个人他们之间认识与否用邻接矩阵表示(1表示认识，0表示不认识)，并A认识B并不意味着B认识A，也就意味着是个有向图。如果一个人是名人，他必须满足两个条件，一个是他不认识任何人，另一个是所有人必须都认识他。

解决问题：

用一个数组保存所有没检查的人的编号，遍历数组中的两个人i，j。如果i认识j，则i必定不是名人，删除i，如果i不认识j，则j必定不是名人，删除j，最终会只剩下一个人，我们检查一下这个人是否是名人即可，如果是，返回这个人，如果不是，那么这n个人中并无名人。

代码：

//初始化数组编号

for(int i=a;i<n;i++){
a[i]=i;
}
while(n>1){
if(known[a[0]][a[1]]){
//如果a[0]号认识a[1]号
//删除a[0]，删除操作用a[n]替换掉a[0]即可，再将n下标减1
a[0]=a[--n];
}else{
//如果a[0]号不认识a[1]号
//删除a[1]
a[1]=a[--n];
}
}
//最终检查a[0]是否为名人

for(int i=0;i<n;++i){

//不考虑自身，并且检查他是否认识某个人，如果认识，那么不是名人
//检查其他人是否认识他，如果有人不认识他，那么他也不是名人
if((a[0]!=i)&&(known[a[0]][i]||!known[i][a[0]]))
return -1;
}
return a[0];
}

算法优化：

以上算法需要用一个数组来保存没有检查的人的编号，意味着空间复杂度为O(n)，是否可以让空间复杂度降低到O(1)呢，答案是肯定的，解决方法就是用一头扫的方法

这里我们就不需要用一个数组来保存没有检查的人的编号了，我们直接对n个人进行html" target="_blank">遍历

遍历的方式是定义两个下标，用两个下标一起往后扫，对于两个下标i,j而言，保证[o~i-1]没有名人，并且[i~j-1]也没有名人，如果i认识j，那么i不是名人，删掉i，删除的方法就是i=j,j++，如果i不认识j，删除j，删除的方式是j++，遍历的时候让j一直加就可以了。

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

算法优化2：

除了一头扫的优化方式，也可以用两头扫的方式优化以上的算法，保证0~i-1没有名人，并且j+1~n也没有名人，如果i认识j，删除i，如果i不认识j，删除j

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