腾讯面试题：64匹马，8赛道，找出最快的4匹最少要几次?-轻识

故事起源

有64匹马，8条赛道，要找出最快的4匹马，最少要几次呢？

初步思考

很多同学可能第一反应就是，这个问题肯定不简单，应该有一些技巧，但技巧是啥呢，又一时想不出来。

其实呢，先别想得太复杂了，比如我现在就问你一个问题，有没有可能存在有一匹不用跑？
答案当然是不行。

分析

那也就是每一匹都得先跑一次，64匹，8个赛道，那就先分8组跑8次。

每一组都会得到8匹的相对速度，也就是在同一组内的名次。

为了方便描述，我们用编号来表示。如A组里面的名次分别用来表示。

因为我们只需要找出最快的4匹，那么肯定不属于最快的4匹，同理把每一组的后4名先排除。

现在每一组内都有相对名次，但不同的组间是不知道的。如果把A组和B组放一起，下面的情况都可能存在。

因为是要找最快的，所以选择每组的第一名再出来跑一次，这样落后的第一名所在的整组都可以排除。为了描述方便，把最快到最慢的第一名所在的组依次重新命名为A，B...H组。

组间的第一名有了名次关系，可以发现一定不属于前4名，因为都在他们前面。同理可排除。同时是最快的，一定属于前4。那接下来只需在剩下的9匹中找出前3。

除去，其余8匹跑一次。如果在第3名或者更后，那说明已经选出了前3名，也不用再跑了，否则再取前3和一起跑一次，即可得结果。

最多11次一定可以选出最快的4匹。

总结

这种思维题，其实是很难直接就想清楚整个过程。可以先想得简单一点，往下推一步再看，逐步推进就可以引导出正确的结果了。

如果喜欢小K的文章，请点个关注，分享给更多的人，小K将持续更新，谢谢啦！



往
期
推
荐
1、全网最全 Java 日志框架适配方案！还有谁不会？
2、Chrome浏览器最新高危漏洞曝光！升级最新版也没用~
3、Spring中毒太深，离开Spring我居然连最基本的接口都不会写了
4、黑客用GitHub服务器挖矿，三天跑了3万个任务，代码惊现中文
5、惊呆了，Spring Boot居然这么耗内存！你知道吗？
6、Gradle真能干掉Maven？今天体验了一把，贼爽！
7、如何重构千行“又臭又长”的类？IntelliJ IDEA 几分钟就搞定！
点分享
点收藏
点点赞
点在看