首页 > 试题广场 >

有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不

[问答题]

有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。

推荐

小海豹

最直观的解决方法是：找到那个任何人都不认识的就是明星；那么
伪代码：

for i=[0,n-1){  
   flag=false; //标识i是否认识敏感词人，如果有认识的人则标识为true  
   for j=[1,n){  
       if(i认识j){  
          flag=true;  
          break;  
       }//end if  
   }//end for  
	     
	   //判断i是否有认识的人  
	   if(flag==false)  
	      return i;    //如果i在剩余的人中没有认识的人，则为明星  
	}//end for

这样的时间复杂度是：o(n*2) 但是这种方法没有充分利用条件：1.如果是明星的话，那么肯定不认识群众；2.如果是群众肯定认识明星。所以：对于1个判断： a与b最多两种可能：1、a认识b，那么a不可能是明星； 2、a不认识b那么b不可能是明星。即每一次比较都会识别一个。所以最多0(n-1)即可识别出哪个是明星：

result=0; //i=0，初始化  
//初始化栈，入栈  
for i=[1,n) {  
  stack.push(i);  
}//end for  
  
  
while(!stack.isEmpty()){  
    temp=stack.pop(); //出栈  
    //判断结果  
    if(temp 认识 result) //result可能是明星  
      result=result;  
    else                 //temp 不认识 result，则temp可能是明星  
      result=temp;    
}//end while

编辑于 2015-02-05 17:29:15 回复(0)