引言
“25匹马找前3名”是算法面试中极具代表性的智力题。给定25匹马和5条赛道，每场比赛最多让5匹马同时赛跑（只能比较相对快慢，无法计时），最少需要多少场比赛才能确定跑得最快的3匹马？直观答案可能是7场或8场，但通过严谨的数学分析可以证明：最少仅需7场比赛。本文将用Java完整模拟这一经典问题，展示如何通过分治策略与淘汰法逐步缩小候选集，最终锁定全局前3名。
问题分析
初始分组策略
将25匹马分为5组（A、B、C、D、E），每组5匹，进行5场初赛：
- 第1-5场：各组内部比赛，确定每组内部排名
关键淘汰赛
第6场：让每组第1名（A1, B1, C1, D1, E1）比赛，假设结果A1 > B1 > C1 > D1 > E1。
这一场比赛蕴含了丰富的淘汰信息：
- A1是全局第1名（击败了所有组第1名）
- D组、E组全部被排除（D1、E1连前5都进不了，其组员更不可能进前3）
- C2及以后被排除（C1最多第3，C2不可能进前3）
- B3及以后被排除（B1最多第2，B2最多第3）
- A4、A5被排除（A1是第1，A2、A3可能争第2、3，但A4不可能）
最终决赛
第7场：仅需比较剩余候选马匹：A2, A3, B1, B2, C1
这5匹马中的前2名（去掉全局第1的A1）即为全局第2、3名。
Java实现
import java.util.*;
/**
* 25匹马找前3名经典问题求解器
* 通过分组赛、淘汰赛与决赛三阶段确定全局前三
*/
public class HorseRacing {
/**
* 马匹类：持有唯一ID和真实速度（模拟用）
*/
static class Horse implements Comparable<Horse> {
final String id;
final double speed; // 真实速度，比赛时不暴露
public Horse(String id, double speed) {
this.id = id;
this.speed = speed;
}
@Override
public int compareTo(Horse other) {
// 按速度降序排列（快的在前）
return Double.compare(other.speed, this.speed);
}
@Override
public String toString() {
return id + "(" + String.format("%.1f", speed) + ")";
}
}
/**
* 模拟一场比赛，返回按名次排序的马匹列表（快的在前）
*/
public static List<Horse> race(List<Horse> horses) {
List<Horse> result = new ArrayList<>(horses);
result.sort(null); // 使用Horse的compareTo按速度排序
return result;
}
/**
* 打印比赛结果
*/
public static void printRace(String name, List<Horse> result) {
System.out.print(name + ": ");
for (int i = 0; i < result.size(); i++) {
System.out.print((i + 1) + "." + result.get(i).id + " ");
}
System.out.println();
}
/**
* 生成25匹速度各不相同的马
*/
public static List<Horse> generateHorses() {
List<Horse> horses = new ArrayList<>();
Random rand = new Random(42);
Set<Double> speeds = new HashSet<>();
// 生成25个唯一速度值
while (speeds.size() < 25) {
speeds.add(rand.nextDouble() * 100);
}
Double[] speedArray = speeds.toArray(new Double[0]);
char group = 'A';
for (int i = 0; i < 25; i++) {
if (i > 0 && i % 5 == 0) group++;
String id = "" + group + (i % 5 + 1);
horses.add(new Horse(id, speedArray[i]));
}
return horses;
}
/**
* 核心算法：7场比赛找前3名
* @param horses 25匹马
* @return 全局前3名
*/
public static List<Horse> findTop3(List<Horse> horses) {
if (horses.size() != 25) {
throw new IllegalArgumentException("需要恰好25匹马");
}
int raceCount = 0;
// === 第一阶段：5场初赛 ===
Map<Character, List<Horse>> groups = new HashMap<>();
List<List<Horse>> groupRaces = new ArrayList<>();
for (int g = 0; g < 5; g++) {
List<Horse> group = new ArrayList<>(horses.subList(g * 5, (g + 1) * 5));
List<Horse> result = race(group);
groups.put((char) ('A' + g), result);
groupRaces.add(result);
raceCount++;
printRace("初赛 " + (char) ('A' + g) + "组", result);
}
// === 第二阶段：第6场，各组第1名对决 ===
List<Horse> groupWinners = new ArrayList<>();
for (int g = 0; g < 5; g++) {
groupWinners.add(groupRaces.get(g).get(0)); // 每组第1名
}
List<Horse> winnerRace = race(groupWinners);
raceCount++;
printRace("淘汰赛（各组冠军）", winnerRace);
// 确定各组在冠军赛中的排名
// winnerRace按速度排序，winnerRace.get(0)是全局最快的组的第1名
Map<Horse, Integer> winnerRank = new HashMap<>();
for (int i = 0; i < 5; i++) {
winnerRank.put(winnerRace.get(i), i);
}
// 确定每组编号
Map<Horse, Character> horseToGroup = new HashMap<>();
for (int g = 0; g < 5; g++) {
char groupName = (char) ('A' + g);
for (Horse h : groups.get(groupName)) {
horseToGroup.put(h, groupName);
}
}
// === 淘汰分析 ===
// 冠军赛第1名所在组 -> 该组的第1名是全局第1
// 冠军赛第4、5名所在组 -> 整组淘汰（不可能进前3）
// 冠军赛第3名所在组 -> 仅保留第1名（最多第3）
// 冠军赛第2名所在组 -> 保留前2名（第2名可能争第2或第3）
// 冠军赛第1名所在组 -> 保留前3名（第2、3名可能争第2、3）
System.out.println("\n=== 淘汰分析 ===");
List<Horse> candidates = new ArrayList<>();
for (int g = 0; g < 5; g++) {
char groupName = (char) ('A' + g);
List<Horse> group = groups.get(groupName);
Horse groupFirst = group.get(0);
int rankInWinnerRace = winnerRank.get(groupFirst);
int keepCount = 0;
if (rankInWinnerRace == 0) keepCount = 3; // 冠军组保留前3
else if (rankInWinnerRace == 1) keepCount = 2; // 亚军组保留前2
else if (rankInWinnerRace == 2) keepCount = 1; // 季军组保留第1
else keepCount = 0; // 第4、5名组全部淘汰
System.out.printf("%c组（冠军赛排名%d）: 保留前%d名 -> ",
groupName, rankInWinnerRace + 1, keepCount);
for (int i = 0; i < keepCount; i++) {
candidates.add(group.get(i));
System.out.print(group.get(i).id + " ");
}
System.out.println();
}
// === 第三阶段：第7场，决赛 ===
// 注意：全局第1已经确定（冠军赛的冠军），决赛是找第2、3名
// 所以决赛的5匹马中的前2名（排除已知的第1）就是全局第2、3
// 但实际上我们已经知道A1（假设A组赢了冠军赛）是第1
// 决赛5匹：A2, A3, B1, B2, C1（假设A>B>C>D>E）
// 这5匹中的前2名就是全局第2、3
System.out.println("\n=== 决赛（确定第2、3名） ===");
// 从候选中移除已确定的全局第1（冠军赛的冠军）
Horse globalFirst = winnerRace.get(0);
candidates.remove(globalFirst);
if (candidates.size() > 5) {
// 正常情况下应该是5匹，如果更多需要截取（理论上不会发生）
candidates = candidates.subList(0, 5);
}
List<Horse> finalRace = race(candidates);
raceCount++;
printRace("决赛", finalRace);
// 组装最终前3名
List<Horse> top3 = new ArrayList<>();
top3.add(globalFirst);
top3.add(finalRace.get(0)); // 决赛第1名是全局第2
top3.add(finalRace.get(1)); // 决赛第2名是全局第3
System.out.println("\n=== 最终结果 ===");
System.out.println("比赛总场次: " + raceCount);
System.out.println("全局第1名: " + top3.get(0));
System.out.println("全局第2名: " + top3.get(1));
System.out.println("全局第3名: " + top3.get(2));
return top3;
}
/**
* 验证算法正确性：与直接排序结果对比
*/
public static void verify(List<Horse> horses, List<Horse> top3) {
List<Horse> sorted = new ArrayList<>(horses);
sorted.sort(null);
System.out.println("\n=== 正确性验证 ===");
System.out.println("直接排序前3名: " + sorted.get(0).id + ", " +
sorted.get(1).id + ", " + sorted.get(2).id);
System.out.println("算法结果前3名: " + top3.get(0).id + ", " +
top3.get(1).id + ", " + top3.get(2).id);
boolean correct = top3.get(0).id.equals(sorted.get(0).id) &&
top3.get(1).id.equals(sorted.get(1).id) &&
top3.get(2).id.equals(sorted.get(2).id);
System.out.println("结果正确: " + correct);
}
/**
* 通用化：N匹马、M条赛道、找前K名的最少比赛场数
* 本问题特化：N=25, M=5, K=3 -> 答案为7
*/
public static void analyzeGeneralCase() {
System.out.println("\n=== 问题泛化分析 ===");
System.out.println("25匹马、5条赛道、找前3名:");
System.out.println(" - 初赛: ceil(25/5) = 5场");
System.out.println(" - 各组冠军赛: 1场");
System.out.println(" - 决赛: 1场（剩余候选不超过5匹）");
System.out.println(" - 总计: 7场（理论下界）");
System.out.println("\n关键洞察：");
System.out.println(" 1. 冠军赛的第4、5名组可直接淘汰整组");
System.out.println(" 2. 冠军赛的第3名组仅第1名可能进前3");
System.out.println(" 3. 冠军赛的第2名组仅前2名可能进前3");
System.out.println(" 4. 冠军赛的第1名组前3名都可能进前3");
System.out.println(" 5. 最终候选集恰好5匹，刚好一场决赛");
}
public static void main(String[] args) {
List<Horse> horses = generateHorses();
System.out.println("25匹马初始状态（速度随机）:");
for (Horse h : horses) {
System.out.print(h.id + "=" + String.format("%.1f", h.speed) + " ");
if (h.id.endsWith("5")) System.out.println();
}
System.out.println();
List<Horse> top3 = findTop3(horses);
verify(horses, top3);
analyzeGeneralCase();
}
}
复杂度分析
- 比赛场次：严格7场，这是理论下界
- 每场比赛：O(M log M) 时间用于排序（M=5，实际为常数）
- 总时间：O(N) 对于固定赛道数M，其中N=25
- 空间复杂度：O(N) 存储马匹信息
最少7场的严谨证明
下界证明：
- 每匹马至少参加1场比赛才有排名依据 → 至少5场初赛
- 5个组的冠军必须互相比较，否则无法确定全局第1 → 至少1场冠军赛
- 经过淘汰后，仍有至少2匹马可能竞争第2、3名 → 至少1场决赛
- 总计下界：5 + 1 + 1 = 7场
本算法达到此下界，因此是最优解。该问题完美展示了信息论下界与分治淘汰的结合：通过每一场比赛最大化排除不可能项，将指数级搜索空间压缩到常数轮次。
