华为OD机试 - 矩阵匹配（Java & JS & Python & C & C++）

题目描述

从一个 N * M（N ≤ M）的矩阵中选出 N 个数，任意两个数字不能在同一行或同一列，求选出来的 N 个数中第 K 大的数字的最小值是多少。

输入描述

输入矩阵要求：1 ≤ K ≤ N ≤ M ≤ 150

输入格式：

N M K

N*M矩阵

输出描述

N*M 的矩阵中可以选出 M! / N! 种组合数组，每个组合数组种第 K 大的数中的最小值。无需考虑重复数字，直接取字典排序结果即可。

备注

注意：结果是第 K 大的数字的最小值

用例

输入	3 4 2 1 5 6 6 8 3 4 3 6 8 6 3
输出	3
说明	N*M的矩阵中可以选出 M！/ N！种组合数组，每个组合数组种第 K 大的数中的最小值； 上述输入中选出数组组合为： 1,3,6; 1,3,3; 1,4,8; 1,4,3; ...... 上述输入样例中选出的组合数组有24种，最小数组为1,3,3，则第2大的最小值为3

题目解析

本题需要我们从矩阵中选取N个元素，这个N元素的特点是：任意两个不能同行同列。

而满足上面条件的N个元素存在多组，我们需要找到着各个组中第K大元素的最小值。

难点一：如何从矩阵中找到N个互相不同行同列的元素呢？

暴力枚举的话，肯定会超时，因此需要寻找更优解法。

根据要求，每行每列只能有一个元素被选择，即可以认为每个行号只能和一个列号进行配对，且配对过的列号不能再和其他行号配对，而形成了配对关系的行号，列号，其实就是一个元素的坐标位置。

因此，找N个互相不同行同列的元素，其实就是在二分图（所有行号一部分，所有列号一部分）找N个边的匹配。

如下图所示

关于二分图的知识可以看下：

HDU - 2063 过山车（Java & JS & Python & C）-CSDN博客

看完上面博客后，我们就可以继续后面说明了。

现在我们已经有了二分图了，也就可以找到具有N个边的"匹配"，但是这种"匹配"可能非常多，难道要全部找出来，然后对比每个"匹配"中第K大，那不还是暴力吗？

题目需要我们多组N个元素中的第K大元素的最小取值，

换位思考一下，假设我们已经知道了第K大的最小取值是kth，那么：

• 检查矩阵中是否至多找到（N - K + 1 个） ≤ kth 的元素值，且这些元素值互不同行同列

N个数中，有K-1个数比kth大，那么相对应的有 (N - (K-1)) = (N - K + 1 ) 个数 ≤ kth。

即找的 N - K + 1 个数中包含了 kth（第K大值）本身。

而kth的大小和二分图最大匹配是正相关的，因为：

每个匹配边 其实就是 行号到列号的配对连线

而行号和列号的组合其实就是坐标位置，根据坐标位置可以得到一个矩阵元素值

因此kth越小，意味着可以找到的 ≤ kth 的矩阵元素越少，相反的，kth 越大，则找到的 ≤ kth 的矩阵元素越多。

因此kth值大小和二分图最大匹配数是线性关系，我们可以使用二分法，来枚举kth。

二分枚举的范围是：1 ~ 矩阵元素最大值，这里不用担心二分枚举到kth不是矩阵元素，因为这种情况会被过滤掉，原因是：我们要找 N - K + 1 个 <= kth 的矩阵元素，最后把关的必然是 kth 本身，即我们必然要在矩阵中找到一个 kth 值，如果二分枚举到的 kth 不是矩阵元素，则无法满足这个要求。

二分枚举到一个kth值：

• 如果kth使得二分图最大匹配 >= N-K+1 个，则说明当前kth取大了，我们应该尝试更小的kth值，即缩小二分右边界为kth-1
• 如果kth使得二分图最大匹配 < N-K+1 个，则说明当前kth取小了，我们应该继续尝试更大的kth值，即扩大二分左边界为kth+1

当二分左右边界重合时的kth值即为题解。

关于二分法，可以看下：

算法设计 - 二分法和三分法，洛谷P3382_二分法与三分法-CSDN博客

JS算法源码

1. const rl = require("readline").createInterface({ input: process.stdin });
2. var iter = rl[Symbol.asyncIterator]();
3. const readline = async () => (await iter.next()).value;
5. void (async function () {
6. const [n, m, k] = (await readline()).split(" ").map(Number);
8. let min = 1;
9. let max = -Infinity;
11. const matrix = [];
12. for (let i = 0; i < n; i++) {
13. matrix.push((await readline()).split(" ").map(Number));
14. max = Math.max(max, ...matrix[i]);
15. }
17. // 二分枚举第K大的最小取值
18. while (min <= max) {
19. // mid就是被枚举出来的N个数中的第K大的最小取值
20. const mid = (min + max) >> 1;
22. // 检查mid作为N个数中第K大值时，是否存在N-K+1个<=它的值
23. if (check(mid)) {
24. max = mid - 1;
25. } else {
26. min = mid + 1;
27. }
28. }
30. console.log(min);
32. function check(kth) {
33. // 利用二分图最大匹配来求解，小于等于kth（第K大值）的元素个数（即二分图最大匹配）
34. let smallerCount = 0;
36. // 记录每个列号的匹配成功的行号
37. // 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为-1
38. const match = new Array(m).fill(-1);
40. // 遍历行号，每个行号对互相心仪的列号发起配对请求
41. for (let i = 0; i < n; i++) {
42. // 记录增广路访问过的列号
43. const vis = new Array(m).fill(false);
44. if (dfs(i, kth, match, vis)) {
45. smallerCount++;
46. }
47. }
49. return smallerCount >= n - k + 1;
50. }
52. function dfs(i, kth, match, vis) {
53. // 行号 i 发起了配对请求
55. // 遍历每一个列号j
56. for (let j = 0; j < m; j++) {
57. // 如果当前列号j未被增广路探索过 && 当前列j行i可以配对（如果行列号位置(i,j)对应矩阵元素值小于等于kth（第K大值），则可以配对）
58. if (!vis[j] && matrix[i][j] <= kth) {
59. vis[j] = true;
61. // 如果对应列号j未配对，或者，已配对但是配对的行号match[j]可以找到其他列号重新配对
62. if (match[j] == -1 || dfs(match[j], kth, match, vis)) {
63. // 则当前行号i 和 列号j 可以配对
64. match[j] = i;
65. return true;
66. }
67. }
68. }
70. return false;
71. }
72. })();

Java算法源码

1. import java.util.Arrays;
2. import java.util.Scanner;
4. public class Main {
5. static int n;
6. static int m;
7. static int k;
8. static int[][] matrix;
10. public static void main(String[] args) {
11. Scanner sc = new Scanner(System.in);
13. n = sc.nextInt();
14. m = sc.nextInt();
15. k = sc.nextInt();
17. int min = 1;
18. int max = Integer.MIN_VALUE;
20. matrix = new int[n][m];
21. for (int i = 0; i < n; i++) {
22. for (int j = 0; j < m; j++) {
23. matrix[i][j] = sc.nextInt();
24. max = Math.max(max, matrix[i][j]);
25. }
26. }
28. // 二分枚举第K大值
29. while (min <= max) {
30. // mid就是被枚举出来的N个数中的第K大值
31. int mid = (min + max) >> 1;
33. // 检查mid作为N个数中第K大值时，是否存在N-K+1个不大于它的值
34. if (check(mid)) {
35. max = mid - 1;
36. } else {
37. min = mid + 1;
38. }
39. }
41. System.out.println(min);
42. }
44. public static boolean check(int kth) {
45. // 利用二分图最大匹配来求解，小于等于kth（第K大值）的元素个数（即二分图最大匹配）
46. int smallerCount = 0;
48. // 记录每个列号的匹配成功的行号
49. int[] match = new int[m];
50. // 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为-1
51. Arrays.fill(match, -1);
53. // 遍历行号，每个行号对互相心仪的列号发起配对请求
54. for (int i = 0; i < n; i++) {
55. // 记录增广路访问过的列号
56. boolean[] vis = new boolean[m];
57. if (dfs(i, kth, match, vis)) smallerCount++;
58. }
60. return smallerCount >= n - k + 1;
61. }
63. public static boolean dfs(int i, int kth, int[] match, boolean[] vis) {
64. // 行号 i 发起了配对请求
66. // 遍历每一个列号j
67. for (int j = 0; j < m; j++) {
68. // 如果当前列号j未被增广路探索过 && 当前列j行i可以配对（如果行列号位置(i,j)对应矩阵元素值小于等于kth（第K大值），则可以配对）
69. if (!vis[j] && matrix[i][j] <= kth) {
70. vis[j] = true;
72. // 如果对应列号j未配对，或者，已配对但是配对的行号match[j]可以找到其他列号重新配对
73. if (match[j] == -1 || dfs(match[j], kth, match, vis)) {
74. // 则当前行号i 和 列号j 可以配对
75. match[j] = i;
76. return true;
77. }
78. }
79. }
81. return false;
82. }
83. }

Python算法源码

1. import sys
3. # 输入获取
4. n, m, k = map(int, input().split())
5. matrix = [list(map(int, input().split())) for _ in range(n)]
8. def dfs(i, kth, match, vis):
9. # 行号 i 发起了配对请求
11. # 遍历每一个列号j
12. for j in range(m):
13. # 如果当前列号j未被增广路探索过 && 当前列j行i可以配对（如果行列号位置(i,j)对应矩阵元素值小于等于kth（第K大值），则可以配对）
14. if not vis[j] and matrix[i][j] <= kth:
15. vis[j] = True
17. # 如果对应列号j未配对，或者，已配对但是配对的行号match[j]可以找到其他列号重新配对
18. if match[j] == -1 or dfs(match[j], kth, match, vis):
19. # 则当前行号i 和 列号j 可以配对
20. match[j] = i
21. return True
23. return False
26. def check(kth):
27. # 利用二分图最大匹配来求解，小于等于kth（第K大值）的元素个数（即二分图最大匹配）
28. smallerCount = 0
30. # 记录每个列号的匹配成功的行号
31. # 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为-1
32. match = [-1] * m
34. # 遍历行号，每个行号对互相心仪的列号发起配对请求
35. for i in range(n):
36. # 记录增广路访问过的列号
37. vis = [False] * m
38. if dfs(i, kth, match, vis):
39. smallerCount += 1
41. return smallerCount >= n - k + 1
44. # 算法入口
45. def getResult():
46. low = 1
47. high = -sys.maxsize
49. for i in range(n):
50. for j in range(m):
51. high = max(high, matrix[i][j])
53. # 二分枚举第K大值
54. while low <= high:
55. # mid就是被枚举出来的N个数中的第K大值
56. mid = (low + high) >> 1
58. # 检查mid作为N个数中第K大值时，是否存在N-K+1个<=它的值
59. if check(mid):
60. high = mid - 1
61. else:
62. low = mid + 1
64. return low
67. # 算法调用
68. print(getResult())

C算法源码

1. #include
2. #include
3. #include
5. #define MAX_SIZE 150
7. #define bool int
8. #define TRUE 1
9. #define FALSE 0
11. int n, m, k;
12. int matrix[MAX_SIZE][MAX_SIZE];
14. bool dfs(int i, int kth, int match[], int vis[]) {
15. // 行号 i 发起了配对请求
16. // 遍历每一个列号j
17. for (int j = 0; j < m; j++) {
18. // 如果当前列号j未被增广路探索过 && 当前列j行i可以配对（如果行列号位置(i,j)对应矩阵元素值小于等于kth（第K大值），则可以配对）
19. if (!vis[j] && matrix[i][j] <= kth) {
20. vis[j] = TRUE;
22. // 如果对应列号j未配对，或者，已配对但是配对的行号match[j]可以找到其他列号重新配对
23. if (match[j] == -1 || dfs(match[j], kth, match, vis)) {
24. // 则当前行号i 和 列号j 可以配对
25. match[j] = i;
26. return TRUE;
27. }
28. }
29. }
31. return FALSE;
32. }
34. bool check(int kth) {
35. // 利用二分图最大匹配来求解，小于等于kth（第K大值）的元素个数（即二分图最大匹配）
36. int smallerCount = 0;
38. // 记录每个列号的匹配成功的行号
39. int match[m];
40. // 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为-1
41. for (int i = 0; i < m; i++) match[i] = -1;
43. // 遍历行号，每个行号对互相心仪的列号发起配对请求
44. for (int i = 0; i < n; i++) {
45. // 记录增广路访问过的列号
46. int vis[MAX_SIZE] = {FALSE};
47. if (dfs(i, kth, match, vis)) {
48. smallerCount++;
49. }
50. }
52. return smallerCount >= (n - k + 1);
53. }
55. int main() {
56. scanf("%d %d %d", &n, &m, &k);
58. int min = 1;
59. int max = INT_MIN;
61. for (int i = 0; i < n; i++) {
62. for (int j = 0; j < m; j++) {
63. scanf("%d", &matrix[i][j]);
64. max = (int) fmax(max, matrix[i][j]);
65. }
66. }
68. // 二分枚举第K大值
69. while (min <= max) {
70. // mid就是被枚举出来的N个数中的第K大值
71. int mid = (min + max) >> 1;
73. // 检查mid作为N个数中第K大值时，是否存在N-K+1个<=它的值
74. if (check(mid)) {
75. max = mid - 1;
76. } else {
77. min = mid + 1;
78. }
79. }
81. printf("%d\n", min);
83. return 0;
84. }

C++算法源码

1. #include
2. using namespace std;
4. #define MAX_SIZE 150
6. int n, m, k;
7. int matrix[MAX_SIZE][MAX_SIZE];
9. bool dfs(int i, int kth, int match[], bool vis[]) {
10. // 行号 i 发起了配对请求
12. // 遍历每一个列号j
13. for (int j = 0; j < m; j++) {
14. // 如果当前列号j未被增广路探索过 && 当前列j行i可以配对（如果行列号位置(i,j)对应矩阵元素值小于等于kth（第K大值），则可以配对）
15. if (!vis[j] && matrix[i][j] <= kth) {
16. vis[j] = true;
18. // 如果对应列号j未配对，或者，已配对但是配对的行号match[j]可以找到其他列号重新配对
19. if (match[j] == -1 || dfs(match[j], kth, match, vis)) {
20. // 则当前行号i 和 列号j 可以配对
21. match[j] = i;
22. return true;
23. }
24. }
25. }
27. return false;
28. }
30. bool check(int kth) {
31. // 利用二分图最大匹配来求解，小于等于kth（第K大值）的元素个数（即二分图最大匹配）
32. int smallerCount = 0;
34. // 记录每个列号的匹配成功的行号
35. int match[m];
36. // 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为-1
37. for (int i = 0; i < m; i++) match[i] = -1;
39. // 遍历行号，每个行号对互相心仪的列号发起配对请求
40. for (int i = 0; i < n; i++) {
41. // 记录增广路访问过的列号
42. bool vis[MAX_SIZE] = {false};
43. if (dfs(i, kth, match, vis)) smallerCount++;
44. }
46. return smallerCount >= n - k + 1;
47. }
49. int main() {
50. cin >> n >> m >> k;
52. int low = 1;
53. int high = INT_MIN;
55. for (int i = 0; i < n; i++) {
56. for (int j = 0; j < m; j++) {
57. cin >> matrix[i][j];
58. high = max(high, matrix[i][j]);
59. }
60. }
62. // 二分枚举第K大值
63. while (low <= high) {
64. // mid就是被枚举出来的N个数中的第K大值
65. int mid = (low + high) >> 1;
67. // 检查mid作为N个数中第K大值时，是否存在N-K+1个不大于它的值
68. if (check(mid)) {
69. high = mid - 1;
70. } else {
71. low = mid + 1;
72. }
73. }
75. cout << low << endl;
77. return 0;
78. }