⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。
在计算机面试中，偶尔会遇到逻辑类题目。由于题目花样百出，准备难度较大，题海战术可能不是推荐的策略。同时，我认为回答问题的思路比答案本身更加重要。在这个专栏里，我将精选一些经典的逻辑思维题，希望能帮助你找到解题思路 / 技巧。
本文是逻辑思维系列的第 1 篇文章，完整文章目录请移步到文章末尾~
- 题目描述
给定 25 匹马与 5 条赛道，一个赛道只能容纳一匹马，每轮比赛只能得到 5 匹马之间的快慢程度，而不是速度，求决胜 1，2，3 名至少多少轮。
- 解题关键
2.1 分治思想
欲求得 25 匹马中的前三名，可以先求得较小规模问题中的前三名，再合并小规模问题的解得出最终解。
2.2 代表元法
在并查集（一种数据结构）中，会使用根节点来代表一个集合，这种方法叫做代表元法。我们可以借鉴这种 “代表元” 的思想，让一组马中跑的最快的一匹来代表整组马。举个例子，给定一组赛马 A1,A2,A3,A4,A5A_1,A_2,A_3,A_4,A_5A1,A2,A3,A4,A5，A1A_1A1为这组马中冠军马，若有 B1>A1B_1>A_1B1>A1，则自然有 B1>AB_1>AB1>A（即：如果 B1B_1B1 比 AAA 组中跑的最快的一匹马还快，自然可以得出 B1B_1B1 比 AAA 组所有马都快的结论）。
提示： 若不了解并查集，请务必阅读我之前写过的一篇文章：《数据结构 | 并查集 & 联合 - 查找算法》
- 解决问题
理解了分治和代表元后，现在可以说问题的解法了，一共分为 2 个回合来解决：
3.1 第一回合
首先，我们将 25 匹赛马分为 5 组，让每组马进行组内比赛，得到组内排名，假设结果为 A1>A2>A3>A4>A5A_1>A_2>A_3>A_4>A_5A1>A2>A3>A4>A5（此时进行了 5 轮比赛）。因为组内排名第四与第五名不可能竞争全场前三名，所以排除每一组的第四与第五名。
A组：{A1,A2,A3,A4,A5}A 组：{A_1,A_2,A_3,A_4,A_5}A组：{A1,A2,A3,A4,A5}
B组：{B1,B2,B3,B4,B5}B 组：{B_1,B_2,B_3,B_4,B_5}B组：{B1,B2,B3,B4,B5}
C组：{C1,C2,C3,C4,C5}C 组：{C_1,C_2,C_3,C_4,C_5}C组：{C1,C2,C3,C4,C5}
D组：{D1,D2,D3,D4,D5}D 组：{D_1,D_2,D_3,D_4,D_5}D组：{D1,D2,D3,D4,D5}
E组：{E1,E2,E3,E4,E5}E 组：{E_1,E_2,E_3,E_4,E_5}E组：{E1,E2,E3,E4,E5}
第一回合
3.2 第二回合
其次，每一组跑得最快的一匹马作为代表元参与一轮 “代表赛”，假设比赛结果是：[A1>B1>C1>D1>E1][A_1>B_1>C_1>D_1>E_1][A1>B1>C1>D1>E1]，由此可以排除失去竞争资格的赛马：
- A1A_1A1 是代表赛中最快的，所以 A1A_1A1 一定是全场第一名；
- B1B_1B1 是代表赛中的第二名，最快情况下 B1B_1B1 同时也是全场的第二名，则 B3B_3B3 前面还有 B2B_2B2，所以 B3B_3B3 失去竞争前三名的资格；
- C1C_1C1 是代表赛中的第三名，最快情况下 C1C_1C1 同时也是全场的第三名，则 C2、C3{C_2、C_3}C2、C3 失去前三名的竞争资格；
- D1D_1D1 和 D1D_1D1 是代表赛的四五名，说明 D 组和 E 组都失去了前三名的竞争资格；
第二回合
3.3 第三回合
此时，剩余的未知顺序的赛马正好有 5 匹，加赛一轮就可以得出第二名和第三名的归属。三个回合总共进行了 7 轮比赛，故答案就是 7。
{A2,A3}{A_2,A_3}{A2,A3}
{B1,B2}{B_1,B_2}{B1,B2}
{C1}{C_1}{C1}
推荐阅读
逻辑思维系列往期回顾：
⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~
本文转载自: 掘金