传说中的google面试题目,赛马问题
well,我是outman。
题目的描述是,有25匹马和5个跑道,(不使用计时工具)要进行几轮比赛才能选出跑的最快的5匹?
我的思路是:用每次比赛的 第3名 去cut在它之后的,最后剩下五匹,选择 3 是因为二分法。详细的过程是这样的:
1,第一组的第三名 计3 编入下一组,
2,可能的情况有5种:
1,2,3,(6,7,8,9 | 4,5) 3在下一组夺冠 V
(1,2 | 6), 3,(4,5 | 7,8,9) 3是亚军
(1,2 | 6,7),3, (4,5|8,9) 第三名
(1,2 | 6,7,8), 3 ,(4,5|9) 第四名
(1,2 | 6,7,8,9), 3 ,4,5 最后一名 ....
因为我们只选前五,所以每种情况都有一些马已经被淘汰了,对应每种情况,保留下来的马是:
1,2,3,(4,5|6,7)
1,2,6,3,(4|7)
1,2,6,7,3
1,2,6,7,8
1,2,6,7,8,9
现在保留下来的马名次都不能准确的确定,那就让他们再赛一次好了。但是除了3,4情况马都比五多,如何选择呢?我们还是知道一些马一定比另一些快的(比如1比2快),于是
对于情况 1,只要4,5,6,7比就可以了
对于2,不确定的是1,2,6的顺序和4,7的顺序,
情况5最复杂,有14种可能,没办法,遇到情况5的时候就比两次吧
总之我们得到了参加过比赛的马中,最快的5匹。这样就回到了问题初始的状态,不断重复这个过程就可以了。复杂度是 O
AS3版本的实现在:
http://wonderfl.net/c/4Byi/
欢迎讨论






最新评论