|
锁定老帖子 主题：讨论一个算法，GOOGLE的一个面试题
精华帖 (8) :: 良好帖 (2) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-10-28
楼上的没有明确回答出至少多少场要比。看不明白至少要多少
|
| 返回顶楼 | |
|
发表时间：2008-10-28
Elminster 写道 《算法导论》第二版，第九章 Medians and Order Statistics，最后一节。那里介绍了一个算法如何通过分组比较来找出一个数组中第 k 大的元素。稍微变一下就是这个问题。
（另：这个是 Google 面试题？不太像啊） 请教下用这个理论是怎么解的？ 我只能通过推理来算，大概是至少比9场吧。 |
| 返回顶楼 | |
|
发表时间：2008-10-28
必须进行的五场比赛就不说了。从第六场比赛开始吧：在每组的第一名进行第六场的比赛，然后第一名直接晋级，再由第一名所在对的下一名和剩下的四匹马进行比赛，以此类推，五轮比赛后即可得出跑的最快的无匹马。
|
| 返回顶楼 | |
|
发表时间：2008-10-28
n/m+y
哈哈 |
| 返回顶楼 | |
|
发表时间：2008-10-28
superloafer,你在上面说，M6正好跑了第七场的第一名结果就出来了，不会吧，其它组也有可能有比M6还要快的呀？应该比下去吧？
|
| 返回顶楼 | |
|
发表时间：2008-10-28
jackyqiang 写道 n/m+y
哈哈 有可能是n/m+y+1, |
| 返回顶楼 | |
|
发表时间：2008-10-29
我觉得至少是6场,5场完了,万一第一场的第5名跑的比后4场的还快,那不是6场就出来了 呵呵,大家觉得呢
|
| 返回顶楼 | |
|
发表时间：2008-10-29
记得有人发了一个意思差不多的题，可以参考一下，那个好像是面试ruby开发的吧
|
| 返回顶楼 | |
|
发表时间：2008-10-29
是7场;
前面5场,让所有的马跑一次; 标记每场的第一名为: A,B,C,D,E; 标记此5匹马为 first梯队 标记每场的第二名为: a,b,c,d,e; 标记此5匹马为 second梯队 第6场, 让 second梯队 跑一次; 标记 顺序为 1,2,3,4,5; 第7场, 让 第6场中跑第1,3,5名的马对应在 first梯队 和 第2,4名在second梯队跑一次 就可以最终确定 前5名马了. |
| 返回顶楼 | |
|
发表时间：2008-10-29
zhangkaitao 写道 我觉得至少是6场,5场完了,万一第一场的第5名跑的比后4场的还快,那不是6场就出来了 呵呵,大家觉得呢
题目中问的是"至少"不是"最少"; 你描述的只是特例; |
| 返回顶楼 | |
