2025 B卷 200分 题型
本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》
华为OD机试真题《矩阵匹配》：
文章快捷目录
题目描述及说明
Java
python
JavaScript
C++
C
GO
题目名称：矩阵匹配
- 知识点：二分查找、DFS搜索、匈牙利算法（二分图匹配）
- 时间限制：1秒
- 空间限制：256MB
- 限定语言：不限
题目描述
从一个 N × M（ N ≤ M）的矩阵中选出 N 个数，要求任意两个数字不能在同一行或同一列。求选出来的 N 个数中第 K 大的数字的最小值。
输入描述
- 输入矩阵要求： 1 ≤ K ≤ N ≤ M ≤ 150。
- 输入格式：
- 第一行： N M K（表示矩阵的行数、列数和目标第 K 大数）。
- 后续 N 行：每行 M 个整数，表示矩阵元素。
输出描述
输出所有合法组合中第 K 大的数字的最小值。无需考虑重复数字，直接按字典序结果计算。
示例
输入：
3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
输出：
3
说明：
所有组合中第2大的数字的最小值为3（如组合[1,3,3]中第2大的数是3）。
Java
问题分析
我们需要在一个N行M列（N ≤ M）的矩阵中选择N个数，每个数不能在同一行或同一列。目标是找到所有可能方案中第K大的数的最小值。这个问题可以通过二分答案和二分图最大权匹配算法（匈牙利算法的扩展）来解决。
解题思路
- 二分答案：假设可能的第K大的值为mid，我们需要验证是否存在一种选法，使得选出的N个数中至少有S = N - K + 1个数 ≤ mid。若能找到这样的mid，则尝试更小的mid；否则需要增大mid。
- 最大权匹配：对于每个mid，构建一个权值矩阵，权值为1（元素 ≤ mid）否则为0。转化为求最大权匹配，判断权值和是否 ≥ S。
代码实现
import java.util.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
static int n, m, k;
static int[][] matrix;
static int[] match;
static int[] labelX, labelY;
static boolean[] visitedX, visitedY;
static int[] slack;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
k = scanner.nextInt();
matrix = new int[n][m];
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = scanner.nextInt();
min = Math.min(min, matrix[i][j]);
max = Math.max(max, matrix[i][j]);
}
}
int left = min;
int right = max;
int ans = max;
int S = n - k + 1;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid, S)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
System.out.println(ans);
}
static boolean check(int mid, int S) {
// 构建权值矩阵：若元素≤mid则权值为1，否则为0
int[][] weights = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
weights[i][j] = (matrix[i][j] <= mid) ? 1 : 0;
}
}
// 初始化KM算法相关数组
match = new int[m];
Arrays.fill(match, -1);
labelX = new int[n];
labelY = new int[m];
slack = new int[m];
// 初始化顶标
for (int i = 0; i < n; i++) {
labelX[i] = -INF;
for (int j = 0; j < m; j++) {
if (weights[i][j] > labelX[i]) {
labelX[i] = weights[i][j];
}
}
}
// 寻找每个左部节点的匹配
for (int u = 0; u < n; u++) {
Arrays.fill(slack, INF);
while (true) {
visitedX = new boolean[n];
visitedY = new boolean[m];
if (dfs(u, weights)) {
break;
}
// 更新顶标
int delta = INF;
for (int j = 0; j < m; j++) {
if (!visitedY[j] && slack[j] < delta) {
delta = slack[j];
}
}
for (int i = 0; i < n; i++) {
if (visitedX[i]) {
labelX[i] -= delta;
}
}
for (int j = 0; j < m; j++) {
if (visitedY[j]) {
labelY[j] += delta;
} else {
slack[j] -= delta;
}
}
}
}
// 计算总权值
int total = 0;
for (int j = 0; j < m; j++) {
if (match[j] != -1) {
total += weights[match[j]][j];
}
}
return total >= S;
}
static boolean dfs(int u, int[][] weights) {
visitedX[u] = true;
for (int v = 0; v < m; v++) {
if (!visitedY[v]) {
int gap = labelX[u] + labelY[v] - weights[u][v];
if (gap == 0) {
visitedY[v] = true;
if (match[v] == -1 || dfs(match[v], weights)) {
match[v] = u;
return true;
}
} else if (slack[v] > gap) {
slack[v] = gap;
}
}
}
return false;
}
}
代码解析
- 输入处理：读取矩阵并确定初始二分范围的最小值和最大值。
- 二分查找：在可能的数值范围进行二分，每次判断当前mid是否可行。
- 构建权值矩阵：将元素≤mid的权值设为1，否则为0。
- KM算法初始化：初始化顶标、匹配数组和松弛数组。
- 寻找增广路径：使用DFS寻找增广路径，调整顶标以扩展匹配。
- 计算总权值：统计匹配边的权值和，判断是否满足条件。
示例测试
- 输入示例1
输入：
3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
输出：3
说明：存在一种匹配使得第2大数为3。
- 输入示例2
输入：
4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
可能的输出：3
说明：选择前三小的数中的合理组合。
- 输入示例3
输入：
2 3 1
3 1 4
2 5 6
输出：3
说明：选择1和3，第1大的数是3。
综合分析
- 时间复杂度：二分法复杂度为O(log(max_val))，每次KM算法复杂度O(n^3)，总复杂度为O(log(max_val) * n^3)，对于n=150能在1秒内完成。
- 空间复杂度：存储矩阵和辅助数组的复杂度为O(n^2)。
- 正确性保障：通过二分答案和最大权匹配确保找到最优解。