第11楼

对于两个人都说对方是好人的情况，要么两个都是好人，要么两个都是坏人。因此可以如下操作 1)对于编号为1,2,...,n的n个人,分别按(1,2),(3,4)...这样配对(当n为奇数时有一人剩余,此人暂放一边),然后选出所有同时说对方是好人的配对。 2)若没有这样的配对.则那么由于超过一半为好人,此时所有配对均为好人与坏人配对.进而n必为奇数,且刚才配对时剩下的那个人必为好人.完毕 3)若至少有一个这样的配对,则从所有这样的配对中各抽出一个人,连同刚才可能剩下的那个人,重新组成序列 1,2,...,m(m<=ceil(n/2)).在这个新序列中超过一半为好人.则对此序列重新跳到步骤1)进行筛选 以上算法最快为O(1),最慢为O(log n) 关闭广告显示

	第12楼

哈哈，有意思啊，思考一下

	第13楼

也有可能死循环啊！ 好人101个，坏人100个 如果100个好人配对 100个坏人配对，坏人全部说谎话！ 那么就陷入了死循环

	第14楼

这时就应该从这100个配对中各选出1人，连同剩余的那个好人，构成新的序列重复刚才的算法。新的序列中有51个好人和50个坏人

	第15楼

先拿出一个人依次与其他人组合，如果他被认为是坏人或好人的次数大于一半，那么他就是坏人（好人）。如果第一个人就被半数以上的人认为是好人，那么他就是好人。时间复杂度为O(n). 最坏的情况是每次挑选的人都是坏人，其他人又都指认他是坏人，这样每一次只能排除一个坏人，时间复杂度为n*k-k*(k+1)/2，应该为O(n^2)

	第16楼

google 面试题 http://www.woofang.com/google.htm

	第17楼

二楼不对

	第18楼

第一步： 有两排凳子两两相对 a1,...,an b1,...,bn 如果有2n个人，就随便坐。如果有2n+1个人就，先挑一个站一边。 第二步： ai和bi 互相说出对方的身份。i=1,..,n 如果ai和bi凳子上的人，说的不一样 和 都说对方是坏人的，两个人就搬凳子走人。（给我消失！）留ai和bi都说对方是好人的。 因为好人比坏人多，所以：如果都走人了，那最先开始站一边的就是答案。                                    如果有剩下的人则：ai和bi凳子上的人，要么都是好人，要么都是坏人。 然后a组剩下的人中，第一个人坐最后一个人的凳子，最后一个人坐倒数第二个人的凳子，然后依次往前，第二个人坐第一个位置。 b组不动 第三步： 重复第二步 直到没有减人，则剩下的都是好人，随便找一个就是答案

	第19楼

最坏情况是：成对坏人，连续出现，并且两人还都说的一样 @：好人          #：坏人    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 a  @  @  #  #  #  #  #  #  #  @  @  @  @  @  @ b  @  @  #  #  #  #  #  #  #  @  @  @  @  @  @ 改进的方法是在第二步最后加以个随即排序,但要保持ai 和bi相对的人始终相对，比如 上面情况随机以后变成：    1   2   3   4   5   6   7   8   9  10   11 12  13  14  15   （新）    4   2   7   8  10  11  15   3   9   1   5  12  13   6  14   （旧） a  #   @   #   #   @   @   @   #   #   @   #   @   @   #   @ b  #   @   #   #   @   @   @   #   #   @   #   @   @   #   @ [此贴子已经被作者于2007-12-14 5:30:55编辑过]

	第20楼

我不会写~~