深蓝黑背景封面:右侧大标题「没有计时器,7 场定前三」,副标题「25 匹马 5 条赛道的分组淘汰推理」;左侧原创示意图——五条纵向赛道上跑着五匹马形圆点,最上方一枚奖牌悬在终点线处,旁边计数牌写着 7;左上标注「面试经典 · 算法」,右上标注「Day 07 · 10-25」 图 1:本文封面,答案是 7 场。

先说明属性:这是一篇经典题解析,题目出自本地历史面试资料,与任何公司的当前招聘无关。题面很短:25 匹马、5 条赛道,每场比赛只能知道同场五匹马的相对名次,没有计时器,问找出全场最快的前三名,最少要比几场?

先把答案立住:7 场。难点不在记住这个数字,而在推出它的那条缩圈逻辑。整道题只有一条推理规则反复使用:一匹马只要被证实「有至少三匹马比它快」,它就和前三名无缘,直接出局。

**第一步:5 场分组赛。**把 25 匹马分成 5 组,每组赛一场,得到每组内部的名次。这一步的意义是把「全场未知」压缩成「五个组内有序」。

**第二步:第 6 场,头马对决。**让五个组的第一名同场比一次。这场做完有两件事被确定:其一,这场的冠军就是全场第一——它赢过本组全部四匹,又赢过其他四组的头马,而其他组的每匹马都慢于自己的头马,传递下来它比全部 24 匹都快;其二,按这场名次给五个组排个序,后面就叫冠军组、亚军组、季军组和第四、第五名组。

**第三步:排除,这是全题的钥匙。**对着六场比赛的结果逐匹问那句「有三匹比它快吗」:第四名组的头马前面有冠军组头马、亚军组头马、季军组头马三匹,整组出局;第五名组同理整组出局;季军组里,第二名前面已经有「冠军组头马、亚军组头马、季军组头马」三匹,所以季军组只有头马还活着;亚军组里,第三名前面有「冠军组头马、亚军组头马、亚军组第二名」,所以亚军组只剩前两匹;冠军组自己,头马已锁定全场第一不再参赛,第四名、第五名前面各有组内三匹更快的,也出局。数一遍:候选只剩五匹——冠军组的第二、三名,亚军组的前两名,季军组的头马。

**第四步:第 7 场,五匹候选决胜。**这场的前两名就是全场第二、第三。第一名早已确定,不参加这场。

解法结构图,分四步缩圈:第一步,25 匹马分成 5 组各赛一场,每组排出内部名次;第二步,各组第一名再赛第六场,按这场名次给组编号,冠军组的头马就是全场第一;第三步开始排除——冠军组的第四、第五名不可能进前三,亚军组只有前三名还有希望,季军组只剩前两名,第四、第五名组整组淘汰,候选从 25 匹缩到 5 匹;第四步,让这 5 匹里的候选马(除已确定的第一名外)赛第七场,前两名即全场第二、第三。图中用灰色叉号标出被淘汰的马,用亮色圈出最终进入决胜局的候选,并给出每步的推理依据:只要「有至少三匹马被证实比它快」,这匹马就出局 图 2:四步缩圈,排除规则是「被证实有三匹更快即出局」。

**为什么 6 场不够,7 场一定够?**光讲道理容易心虚,直接写代码验证。思路:给 25 匹马随机生成隐藏的真实速度(人看不到,只能通过比赛拿到名次),严格按上面的七场方案执行,最后比对算法给出的前三和真实前三。用 Node.js 22.15.0 直接运行(node horses.js):

'use strict';

// 可复现随机数(固定种子,输出稳定)
function mulberry32(seed) {
  return function () {
    seed |= 0; seed = (seed + 0x6D2B79F5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

// 跑一遍完整方案:25 匹马有隐藏的真实速度,人只能比赛看名次
function runOnce(rand) {
  const horses = Array.from({ length: 25 }, (_, id) => ({ id, speed: rand() }));
  // 第 1~5 场:分 5 组,各赛一场,组内排出名次
  const groups = [];
  for (let g = 0; g < 5; g++) {
    groups.push(horses.slice(g * 5, g * 5 + 5).sort((a, b) => b.speed - a.speed));
  }
  // 第 6 场:各组头马对决,按名次给组排序(groups[0] 是冠军组)
  groups.sort((g1, g2) => g2[0].speed - g1[0].speed);
  // 排除后只剩 5 匹候选:冠军组第 2、3 名,亚军组前 2 名,季军组头马
  const candidates = [groups[0][1], groups[0][2], groups[1][0], groups[1][1], groups[2][0]];
  // 第 7 场:候选对决,前两名即全场第二、第三(第一是冠军组头马)
  candidates.sort((a, b) => b.speed - a.speed);
  const answer = [groups[0][0].id, candidates[0].id, candidates[1].id];
  const truth = [...horses].sort((a, b) => b.speed - a.speed).slice(0, 3).map((h) => h.id);
  // 顺带记录:只赛 6 场时,真正的全场第二名落在哪一组
  return { ok: answer.join() === truth.join(), secondGroup: groups.findIndex((g) => g.some((h) => h.id === truth[1])) };
}

const N = 100000;
let pass = 0;
const secondAt = [0, 0, 0, 0, 0];
const rand = mulberry32(20261025);
for (let i = 0; i < N; i++) {
  const r = runOnce(rand);
  if (r.ok) pass++;
  secondAt[r.secondGroup]++;
}
console.log(`随机 ${N} 种速度分布,7 场方案找对前三:${pass}/${N}`);
console.log(`只赛 6 场时,真实第二名的分布:冠军组第 2 名 ${secondAt[0]} 次,亚军组头马 ${secondAt[1]} 次,其余组 ${secondAt[2] + secondAt[3] + secondAt[4]} 次`);

实测输出:

随机 100000 种速度分布,7 场方案找对前三:100000/100000
只赛 6 场时,真实第二名的分布:冠军组第 2 名 16689 次,亚军组头马 83311 次,其余组 0 次

第一行说明七场方案在十万种随机速度分布下全部找对。第二行是「6 场不够」的实锤:赛完六场后,真实的全场第二名有时是冠军组的第二名、有时是亚军组的头马——两种可能都会真实出现,不加赛第七场就无法确定,所以 7 场既是充分的也是必要的。

**常见误区。**一是上来想「一场定胜负」,25 匹马无法同场,此路不通;二是试图变相计时,比如「多比几次取平均」,题目明确没有计时器,相对名次是唯一信息;三是排除时只敢整组淘汰,漏掉组内排除——其实亚军组的第三、四、五名同样满足「三匹更快」,敢用到组内这一层,候选才能收敛到五匹;四是以为第六场之后按组排座次就能直接读出全场名次,实测数据已经说明不行。

跳出题目看,这是一种「只能小组比较、无法全局排序」场景下的成本控制思维——锦标赛排序、两两对比评测都是同构问题:比较次数就是预算,每比一场都要让排除面尽量大。你第一次见这道题时,给出的答案是几场?欢迎分享。