腾讯算法面试题：64匹马8个跑道需要多少轮才能选出最快的4匹？

一、题目分析

首先没有计时器，不要想象成奥运会的赛跑比赛，一轮比赛解决不了问题。

这64匹马速度是恒定的，不会因为再跑一轮累了跑的就比其他马慢，否则这题没有办法解了。

8个赛道的意思是每一轮都能跑8匹马，不会跑乱了。

如果“马”赛跑的让你思维干扰很大，可以想象为64个速度未知且速度各不相同且速度恒定不变的玩具小汽车，8个跑道是直的，每次8个小汽车比赛。

二、解题思路

首先可以把64个小汽车分为8组，分别比赛，在每组中的不能进入前四位的，那说明在64个中肯定不能进入前四位，即每组后四位肯定不是我们想要的答案。

接下来剩下了32个速度不同的小汽车，如果我们继续使用上面的方法，32组再次拆分，分为4组，挑出来最快的4个，这四个是最快的吗？当然不是，如果4组中，第一组的第2名跑的比第二组的第一名还快呢？

换个思路，把第一步中的八组里的第1名都放一起比一下，可以挑出后四名，而这后四名分别是他们各自分组下的第1名，此时便可以淘汰掉对应的这四组，剩下了16个小汽车。

接下来我们将剩下的16个小汽车来做一个表格组合一下。

上面的表格中我们默认排序为A，B，C，D是刚才第三步中的各个小组的第一，我们可以看看目前的一些小汽车速度关系。

再来列一下我们要的最快的四辆可能会出现哪几种情况。

1.如果除了各组第1，每一组的第2进行比较的话，若D1最大，则我们要的答案是ABCD，此时说明D1，D2，D3无论如何都不会进入前四。

2.如果除了各组第1，每一组的第2进行比较的话，若C1最大，且C1>D，则我们的答案是ABCC1，说明C2，C3不会进入前四。

3.如果除了各组第1，每一组的第2进行比较的话，若B1最大，而且B1>D且B1<C，则我们的答案是ABCB1；或者B1>C且B1>D，则此时的速度排列是A>B>B1，要用B2去和剩下的C，D，A1去比较，取到第四名，从而看出B3的速度无论如何都不能进前四。

4.如果除了各组第1，每一组的第2进行比较的话，若A1最大，并且A1>B，则前两名为A，A1，这时候需要A2和B比较，若A2>B，则前三名为A，A1，A2，再拿A3和B比较，可以看出A，A1，A2，A3都是有可能出现在前四名中的。

通过上面的a，b，c，d四步可以推测出，D1，D2，D3，C2，C3，B3这六辆小汽车的速度无论如何是进不了前四了。

1. 按照上一步的结果我们可以看下图，我们只需要在棕色找我们需要的答案即可。

此时我们可以确定这剩下的10辆小车里面肯定有我们要的答案，而且可以确定的是A肯定是所有小车里跑的最快的那一个，然后我们只需要在剩下的九辆车里找出最快的三辆即可。

1. 我们可以任意在9辆车里取8辆进行比较，取出前三名，然后拿剩下的之前一个这三名比较，则可以得出我们想要的最快的四辆车。但是如果是这样的话，我们需要比试两轮，有更好的办法减少比赛的轮次吗？接着往下看。

2. 目前剩下的9辆小汽车里，我们可以确定B，C，D，B1，B2，C1这六辆车里B肯定是速度最大的，而A1，A2，A3中A1肯定是速度最大的。

3. 我们先假定B是前四名中的小汽车，只比较除了B的其余八辆车，而我们只需要去这八辆车里的前两名，如果这八辆车里最快的是 C或者B1，那么B肯定属于前四名中的一辆，则这一轮即可完成比较，我们想要的答案是AB和这一轮的前两名。

4. 如果八辆车里最快的是 A1，则我们要看这八辆车里第二快的是哪一辆，如果第二快的是C或者B1那此时也可以确定之前假定的B小车肯定是进了前四名的，只是不确定是不是 排在第二名的位置，则也可以在这一轮即可完成比较，我们想要的答案是ABA1还有C或者B1。

5. 如果八辆车里最快的是 A1，且第二快的是A2，则需要看排第三的是哪一辆车，如果是C或者B1而不是A3，那也可以说明B肯定是可以进前四名的，只是顺序问题不可保证。

6. 如果八辆车里的前三排序是 A1，A2，A3，那这种情况则将B和A3两辆车拿出来比赛一轮，谁快谁即是前四名中的一个。

三、答案总结：

从上面十一步的思路分析中我们可以看到，除了第11步这种情况下我们只需要通过8+1+1=10轮就可以找出前四名小汽车，但是如果出现了第11种这种情况后，我们则需要多加一轮，也就是8+1+1+1=11轮次，挑出64辆小汽车最快的4辆小车。