|
锁定老帖子 主题：讨论一个算法，GOOGLE的一个面试题
精华帖 (8) :: 良好帖 (2) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-10-30
superloafer 写道 jemmywang 写道 ls的，现在是选前5最快的。
如果D组第一是第一梯队最慢的（第5），那D组从第2名以后怎么也不可能挤入前5了； 注意题目，是问至少： 答案是7场，下面是我的表述： 前5场的比赛以后取每组第一进行比赛（第6场），排名如下所示： 1 2 3 4 5 a e j o t b f k p u c g l q v d h m r w e i n s x 在第6场中排名第5的那组，从第2名以下 无法进入前5，同理可知，第4名那一组自第3名以下无法进入前5.。。。。，如下： 1 2 3 4 5 a e j o t b f k p X c g l X X d h X X X e X X X X 第7场，取第6场的第5名与 第6场的前4名所在的组的第2名进行比赛，如果这些第2名都比第6场第5名慢，那么第6场第5名就是前5的最后一个，前5名就诞生了。 (题目的至少到这里就得到了解答。 如果不满足这种情况，则淘汰比第6场第5名还慢的那组自第2名开始的所有马，剩下的情况就比较简单了，看着也知道10场绝对能得到最快的5匹。 我觉得你的是对的，我前面也说过这样排除那些不需要比赛的，但是得出的结果是八场。但是这道题目说的是至少，所以如果能找到一种比赛组合可能七场就能确定的话，那应该就是七场了。我没有抓住题目的要旨，即“至少”。就好比一个排序算法一样，拿插入排序为例，如果问插入排序至少要比较多少次才能确定它是有序的，答案是n，当所有的数据本来都是顺序排列的时候；当问至多要比多少才能确定呢，答案是(n-1)n/2次，即所有的数据都是逆序的。 你的第一步是对的，但第二步却有点问题，太过理想化，如果按你的思想，拿某一轮的第五和其他4轮的第一比，如果第五跑第一，那么结果是6场，所以这种算法肯定是错误的。 应该拿每组的第二名比赛 a e j o t 1（根据第六轮分析） b f k X X 2（因为e,b比f快，所以a比f快，所以f后面至多一个，为k） c ◎ X X X 3（abcef比◎快，所以◎和后面的都淘汰） d X X X X 4（同上） e X X X X 5（同上） 这样根据比赛排名（每组的第二排名）， 可以淘汰如上X 然后拿j，f，c，d，e比赛 无论排名如何都能得出结果(自己分析) 至少7场 |
| 返回顶楼 | |
|
发表时间：2008-10-31
用插入排序法给一个数组排序，至少要n次比较，就是当数据都是顺序的时候，因为只有比过n次之后你才知道数组已经是排好序的。这时候问你用这个算法至少要比较数据几次，就要回答n；用顺序查找或二分查找法查找一个数据，最差和一般情况的时间复杂度分别为O(n)和O(lgn)，但是如果问至少几次可以找到呢？两者都为一次，因为就是理想情况下一戳就中。
这个题目就算马匹的排序完全理想，也不可能在第六场找出前五名来。当第六场跑第五的马和其他队的第二的马（不包括它自己队的队员）进行第七场比赛跑一次，“理想”情况下他要是跑了第一名把各队的第二都赢了，第七场就能出结果了。这个题目的理想情况就是:在第六场跑出来的五匹马其实就是前五名了，但是除了第一名之外的其他2，3，4，5名都还没有跟其他队剩下的队员比赛，他们无法证明自己就是真正的前五。好，这个时候，最快速的证明方法就是把他们当中实力最弱的第五的马拉出去战斗，和各队（除了它自己的队员外）中最厉害的第二名比一场，立马就可见分晓。他要是赢了的话，就可以给自己和第六场的第二，三，四名正身了。这道题目问的就是“至少”，而要达到这种“至少”本来就是要算法和数据都要对路的情况下才行！ |
| 返回顶楼 | |
|
发表时间：2008-10-31
哈哈，没看请题目。
我改下以前的答案。 好像应该是10场。 第六场比赛后 都让没次比赛都是最快的5五匹马比赛。 最坏的情况是五匹马全在一个组里 应该最少是10场吧 |
| 返回顶楼 | |
|
发表时间：2008-10-31
扩展之后的话 如果N/M能整除的话
是不是就是N/M+Y场呢 呵呵 |
| 返回顶楼 | |
|
发表时间：2008-10-31
同意 lipengyu2006 我也认为是10次
前5次得到前5名，然后让这5名比，第一名 为最快的，然后用第一名所在的组的第二名和其余刚才4个比 ，依次类推 至少需要10次 |
| 返回顶楼 | |
|
发表时间：2008-10-31
貌似很多人都误解了‘至少’
至少 意思就是在任何情况下，必须比这么多场次才可以得出最快的5匹马，所以要考虑最差情况 |
| 返回顶楼 | |
|
发表时间：2008-10-31
kissau 写道 superloafer 写道 jemmywang 写道 ls的，现在是选前5最快的。
如果D组第一是第一梯队最慢的（第5），那D组从第2名以后怎么也不可能挤入前5了； 注意题目，是问至少： 答案是7场，下面是我的表述： 前5场的比赛以后取每组第一进行比赛（第6场），排名如下所示： 1 2 3 4 5 a e j o t b f k p u c g l q v d h m r w e i n s x 在第6场中排名第5的那组，从第2名以下 无法进入前5，同理可知，第4名那一组自第3名以下无法进入前5.。。。。，如下： 1 2 3 4 5 a e j o t b f k p X c g l X X d h X X X e X X X X 第7场，取第6场的第5名与 第6场的前4名所在的组的第2名进行比赛，如果这些第2名都比第6场第5名慢，那么第6场第5名就是前5的最后一个，前5名就诞生了。 (题目的至少到这里就得到了解答。 如果不满足这种情况，则淘汰比第6场第5名还慢的那组自第2名开始的所有马，剩下的情况就比较简单了，看着也知道10场绝对能得到最快的5匹。 我觉得你的是对的，我前面也说过这样排除那些不需要比赛的，但是得出的结果是八场。但是这道题目说的是至少，所以如果能找到一种比赛组合可能七场就能确定的话，那应该就是七场了。我没有抓住题目的要旨，即“至少”。就好比一个排序算法一样，拿插入排序为例，如果问插入排序至少要比较多少次才能确定它是有序的，答案是n，当所有的数据本来都是顺序排列的时候；当问至多要比多少才能确定呢，答案是(n-1)n/2次，即所有的数据都是逆序的。 你的第一步是对的，但第二步却有点问题，太过理想化，如果按你的思想，拿某一轮的第五和其他4轮的第一比，如果第五跑第一，那么结果是6场，所以这种算法肯定是错误的。 应该拿每组的第二名比赛 a e j o t 1（根据第六轮分析） b f k X X 2（因为e,b比f快，所以a比f快，所以f后面至多一个，为k） c ◎ X X X 3（abcef比◎快，所以◎和后面的都淘汰） d X X X X 4（同上） e X X X X 5（同上） 这样根据比赛排名（每组的第二排名）， 可以淘汰如上X 然后拿j，f，c，d，e比赛 无论排名如何都能得出结果(自己分析) 至少7场 第7轮不一定能得出结果。 首先，LS的e在两个队伍里，假设这个是LS的假设: a y j o t 1（根据第六轮分析） b f k X X 2（因为e,b比f快，所以a比f快，所以f后面至多一个，为k） c ◎ X X X 3（abcef比◎快，所以◎和后面的都淘汰） d X X X X 4（同上） e X X X X 5（同上） 我把 A组的e改成y了。 如果c跑得最快，d跑得第二快，这个时候 @，e，y，b都有可能是第4、5名。 |
| 返回顶楼 | |
|
发表时间：2008-10-31
我也并不知道标准答案，下面是我的思路:
第6轮完毕是 A组 A1,A2,A3,A4,A5 B组 B1,B2,B3,B4,-- C组 C1,C2,C3,--,-- D组 D1,D2,--,--,-- E组 E1,--,--,--,-- 假设 A1>B1>C1>D1>E1 第二名没有什么悬念，肯定是A2,B1中的一个 第三名也没有悬念，是A2,A3,B1,B2,C1中的一个 所以拿A2,B1,A3,B2,C1 比一轮 （第7轮），那么可以得出第2、3名，并且可以淘汰第5名，以及第5名所在的其余成员 下面的就麻烦了。 1. 最简单情况，如果A2，A3是前两名，那么第4、5名就是A4,A5,B1,B2,C1里面，再比第8轮就可以 2. 如果A2,B1是前两名，再比第8轮也可以得出结果。我就不仔细分析了。 3. 最复杂的情况就是B1和C1是前两名， 3.1 如果A3是最后一名，剩下 A组 A1,A2,--,--,-- B组 B1,B2,B3,--,-- C组 C1,C2,C3,--,-- D组 D1,D2,--,--,-- E组 E1,--,--,--,-- 这里就有A2,B2,B3,C2,C3,D1,D2,E1 8匹马来竞争最后的2个名额. A2,B2比过，所以 第4名可以在 A2,B2中的快者，然后加上C2,D1中比出来，假设我第8轮只用3匹马比，可以得出第4，而且可以淘汰第3名以及比第3名慢的马。所以第8轮可以至少淘汰2匹，加上选出来的第4，那么第9轮只剩下5匹马了，可以得出结果。 3.2 如果B2是最后一名，剩下 A组 A1,A2,A3,--,-- B组 B1,--,--,--,-- C组 C1,C2,C3,--,-- D组 D1,D2,--,--,-- E组 E1,--,--,--,-- 可以发现这个图比上面的还简单，所以不会比3.1多 综上，觉得至少应该比9轮 |
| 返回顶楼 | |
|
发表时间：2008-10-31
下图是对ls的做法的补充说明
该图表示的是第7场比赛(在A2,B1,A3,B2,C1之间进行的比赛)之后的结果 其中 “○”表示已经确定是前5名之内的马 “-”表示在第6场比赛后淘汰（不可能进前5）的马 “×”表示第7场比赛之后根据结果淘汰的马 淘汰的依据是反证法：假定该马能够进入前5名，那么会有多于5匹马进入前五名 黄色底色的是参加第7场比赛的马 黄色底色的“○”，“×”以外的马与蓝色底色的马进行第8场比赛 第八场比赛的第一是第4名 第7场比赛前两名是A2,A3的情况下 第八场比赛的第二就是第5名 之外的情况下，第八场比赛的第二与绿色底色的马进行第9场就可以得到第5名 |
| 返回顶楼 | |
|
发表时间：2008-10-31
LS的赞一个，很清晰
|
| 返回顶楼 | |
