解一道经典的腾讯算法面试题（小白也能看懂）

算法，对于一个程序员还是非常重要的，它不单单能体现你的数学思维，还能体现出一种逻辑能力，如果你要进BAT这样的大厂，请一定重视算法，它是你的必经之路。

前两天看到的一道腾讯面试题，觉得还是很经典，分享一下自己对于解答这道题的思路，本文不长，但是只要认真去看，跟着我的思路，还是足够教你一种解题思维，如果看完还不会，请留言，我一定教会你。

一. 题目

有64匹马，一共有8个赛道，想要找出最快的4匹马，要比赛最少多少轮才可以?

看完题目请自己先思考一下怎么解，然后带着你的答案再往下看。

二. 题目分析

1. 首先没有计时器，不要想象成奥运会的赛跑比赛，一轮比赛解决不了问题。
2. 这64匹马速度是恒定的，不会因为再跑一轮累了跑的就比其他马慢，否则这题没有办法解了。
3. 8个赛道的意思是每一轮都能跑8匹马，不会跑乱了。
4. 如果“马”赛跑的让你思维干扰很大，可以想象为64个速度未知且速度各不相同且速度恒定不变的玩具小汽车，8个跑道是直的，每次8个小汽车比赛。

三. 解题思路

1. 首先可以把64个小汽车分为8组，分别比赛，在每组中的不能进入前四位的，那说明在64个中肯定不能进入前四位，即每组后四位肯定不是我们想要的答案。
2. 接下来剩下了32个速度不同的小汽车，如果我们继续使用上面的方法，32组再次拆分，分为4组，挑出来最快的4个，这四个是最快的吗？当然不是，如果4组中，第一组的第2名跑的比第二组的第一名还快呢？
3. 换个思路，把第一步中的八组里的第1名都放一起比一下，可以挑出后四名，而这后四名分别是他们各自分组下的第1名，此时便可以淘汰掉对应的这四组，剩下了16个小汽车。
4. 接下来我们将剩下的16个小汽车来做一个表格组合一下。

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

A>B>C>D
A>A1>A2>A3
B>B1>B2>B3
C>C1>C2>C3
D>D1>D2>D3

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

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这六辆小汽车的速度无论如何是进不了前四了。

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

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

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

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

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

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

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

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

四. 答案总结：

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

如果看一遍觉得不能理解的话，请多看两遍，如果还有问题请留言。

如果对你有帮助不要忘了分享给你的朋友或者点击右下方的“在看”哦！也可以关注作者，查看历史文章并且关注最新动态，助你早日成为一名全栈工程师！