google面试题[讨论]

《google面试题[讨论]》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、google面试题［讨论］有n个人，其屮超过半数是好人，剩下的是坏人好人只说真话，坏人可能说真话也可能说假话这n个人互相都知道对方是好人述是坏人现在要你从这n个人当屮找出一个好人來，只能通过以下方式:每次挑出两个人，让这两个人互相说出对方的身份，你根具两个人的话进行判断。问通过何种方法才能最快的找出一个好人来，（要考虑最坏的情况）我现在提一个想法，望大家指止先找一个人A,然后其他所有人评价A1如果半数说A是好人：A是好人2如果半数以上说A是坏人：A是坏人如果A是坏人去掉说A是好人的人（一定是坏人）在剩下的人里找一个人重复上面的（这里好人肯定更多于一•半）递归进行最坏情况就是坏人都说实，话且每

2、次运气不好都选出的是坏人这时复杂度是0（n平方）实际计算时选出好人的几率越来越高的，因为坏人不断的被去掉大家有何高见》？最坏的情况时所有坏人都被选出，前所有坏人说真话，这时才选出好人，最坏情况o（nA2）最好情况o（n）google面试题……我的解法路过看了楼主的算法，觉得无法接受，应该是最慢的一个算法，下面是我的想法：思想是尽量多的排除坏人：1,如果两个人都说对方是好人，那么有两种可能，要吗都是好人,要吗都是坏人2,如果有一个人说对方是坏人，那么两人种至少有一个坏人可以同吋排除，剩下的人照样满足条件好人站半树以上，再在剩下的人中找好人intpeopled={0丄1,1丄0,0,0,1};/

3、収个人的数组1是好人,0是坏人intsamePos=-1,sameNum=・1;while（i

4、(n),最快n/2,最慢n.写的不太严密，请人家指正.我的想法,前提：被选出的人町以被一直重复选出；:如果N为偶数，所以至少有N/2个好人，取整I好人■坏人1＞二1(实际N为偶数的时候:I好人■坏人1＞二2);好人肯定说真话,保证了结论的正确性＞=50%,任选A,所有人评A,比较结论，评出的结果，X:好人，Y:坏人，A=X＞Y?好人:坏人；:同样的道理，N为奇数，有一样的结果。存在边界的情况：好人比坏人只多一人，X==Y；说明A为好人人。因为就算坏人都说假话，起码也有一半的真话。所以整个算法的复杂度为0(N).请各位赐教！1來去如风的思路不错：与查找众数的方法一样，通过不断的除去坏人与好人來

5、利用好人超过半数的条件：如果有一个人说对方是坏人,那么两人种至少有一个坏人，可以同时排除，剩下的人照样满足条件好人站半树以上，再在剩下的人屮找好人。楼上(天涯客)的可能没有看清楚耍找出好人的耍求。如果A是外人的话，那么你的评选还要继续下去。照来去如风的思路:如果两个人都说对方是好人，那么有两种可能,耍吗都是好人，耍吗都是坏人.在此基础上，可以把这些人分为两组,A和B;a是A组的,a和x都说对方是好人，把x加到A组，否则加到B组,，哪一组的人数先过半数了，这组就是好人，另外一组就是坏人了.时间复杂度o(n),最快n/2,最慢n..实firstwai几乎谈到重点了，来去如风的分析有问题。。明天得

6、闲写下，哈哈最慢是[n/2]+1最快是[n/2]这个好像就是算法导论上的课后习题，当时就没做出來对于两个人都说对方是好人的情况，要么两个都是好人，要么两个都是坏人。因此可以如下操作1)对于编号为1,2,…,n的n个人，分别按(1,2),(3,4)…这样配对(当n为奇数时有一人剩余，此人暂放一边),然后选出所有同时说对方是好人的配对。2)若没有这样的配对.则那么由于超过一半为好人，此时所有配对均为好人与坏人配对.进而n必为奇数，且刚才配对时剩下的那个人必为好人.完毕3)若至少有一个这样的配对，则从所有这样的配对屮各抽出一个人，连同刚才可能剩下的那个人,重新组成序列1,2,...,m(m<=ce

7、il(n/2)).在这个新序列屮超过一半为好人.则对此序列重新跳到步骤1)进行筛选以上算法最快为0(1),最慢为O(logn)也有可能死循环啊！好人1()1个，坏人10()个如果10()个好人配对100个坏人配对，坏人全部说谎话！那么就陷入了死循环这时就应该从这100个配対中各选出1人，连同剩余的那个好人，构成新的序列重复刚才的算法。新的序列中有51个好人和5()个坏人先拿出一个人依次与其他人组合，如果他被认