欢迎来到天天文库
浏览记录
ID:30776956
大小:81.50 KB
页数:11页
时间:2019-01-03
《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(i4、(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<=ce7、il(n/2)).在这个新序列屮超过一半为好人.则对此序列重新跳到步骤1)进行筛选以上算法最快为0(1),最慢为O(logn)也有可能死循环啊!好人1()1个,坏人10()个如果10()个好人配对100个坏人配对,坏人全部说谎话!那么就陷入了死循环这时就应该从这100个配対中各选出1人,连同剩余的那个好人,构成新的序列重复刚才的算法。新的序列中有51个好人和5()个坏人先拿出一个人依次与其他人组合,如果他被认
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()个坏人先拿出一个人依次与其他人组合,如果他被认
此文档下载收益归作者所有