一. 题目-矩阵匹配
从一个NM（N<=M)的矩阵中选出N个数，任意两个数字不能在同一行或同一列，求选出来的N个数中第K大的数字的最小值是多少。
输入描述：
输入矩阵要求：1<=K<=N<=M<=150
输入格式：N M K
NM矩阵
输出描述：
N*M的矩阵中可以选出M!/N!种组合数组，每个组合数组中第K大的数中的最小值。无需考虑重复数字，直接取字典排序结果即可。
补充说明：注意：结果是第K大的数字的最小值
示例1
输入：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个数字的组合：
- 使用itertools.combinations或其他方法从给定的矩阵中生成所有包含N个数字的可能组合。
-
计算每个组合中第K大的元素：
- 对于每个生成的组合，按降序对数字进行排序并选择第K个元素。这就是该组合中第K大的元素。
-
收集所有第K大的元素：
- 将从每个组合中获得的第K大的元素存储在一个列表中。
-
对第K大的元素列表进行排序：
- 对第K大的元素列表按升序进行排序。
-
输出排序后的列表中的最小元素：
- 输出排序后的列表中的第一个元素，即为第K大的数字的最小值。
三.题解代码
Python题解代码
from itertools import combinations
def find_min_kth_largest(matrix, k):
n = len(matrix)
m = len(matrix[0])
all_combinations = list(combinations(range(m), n))
min_kth_largest = float('inf')
for comb in all_combinations:
selected_numbers = [matrix[i][j] for i, j in enumerate(comb)]
selected_numbers.sort(reverse=True)
min_kth_largest = min(min_kth_largest, selected_numbers[k-1])
return min_kth_largest
JAVA题解代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[][] matrix = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = sc.nextInt();
}
}
List<Integer> result = new ArrayList<>();
findCombinations(matrix, new boolean[M], 0, N, new ArrayList<>(), result);
Collections.sort(result);
System.out.println(result.get(K - 1));
}
private static void findCombinations(int[][] matrix, boolean[] visited, int start, int count, List<Integer> current, List<Integer> result) {
if (count == 0) {
List<Integer> temp = new ArrayList<>(current);
Collections.sort(temp);
result.add(temp.get(temp.size() - K));
return;
}
for (int i = start; i < matrix.length; i++) {
if (!visited[i]) {
visited[i] = true;
for (int j = 0; j < matrix[i].length; j++) {
current.add(matrix[i][j]);
findCombinations(matrix, visited, i + 1, count - 1, current, result);
current.remove(current.size() - 1);
}
visited[i] = false;
}
}
}
}
C/C++题解代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k;
int matrix[150][150];
bool used[150];
vector<int> ans;
void dfs(int row, int col, int depth) {
if (depth == n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!used[j]) {
ans.push_back(matrix[i][j]);
}
}
}
sort(ans.begin(), ans.end());
return;
}
for (int i = col; i < m; i++) {
if (!used[i]) {
used[i] = true;
dfs(row + 1, i + 1, depth + 1);
used[i] = false;
}
}
}
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> matrix[i][j];
}
}
dfs(0, 0, 0);
cout << ans[k - 1] << endl;
return 0;
}
JS题解代码
// 引入readline模块
const readline = require('readline');
// 创建readline接口实例
const rl = readline.createInterface({
input: process.stdin, // 设置输入流
output: process.stdout // 设置输出流
});
let n, m, K, mx; // 定义变量
let myMap = []; // 初始化二维数组
// 逐行读取输入
rl.on('line', (line) => {
if (!n) { // 如果n未定义
[n, m, K] = line.split(' ').map(Number); // 读取行数、列数和K值
mx = 0; // 初始化mx
} else {
const row = line.split(' ').map(Number);
myMap.push([0, ...row]);; // 读取二维数组数据
mx = Math.max(mx, ...row); // 更新mx
}
}).on('close', () => { // 读取完毕后执行
console.log(solve(mx)); // 输出结果
});
// 二分第k大的值的大小
function solve(mx) {
let l = 1, r = mx;
let ans = 0;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
// 将小于等于p的元素设为True，大于p的元素设为False，构建匹配图
function check(p) {
const mp = myMap.map(row => row.map(val => val <= p));
let ans = 0;
const match = new Array(m + 1).fill(0);
for (let i = 1; i <= n; i++) {
const chw = new Array(m + 1).fill(true);
if (findMuniu(i, mp, chw, match)) {
ans++;
}
}
return ans >= n - K + 1;
}
// 这里就是一个匈牙利匹配
function findMuniu(x, mp, chw, match) {
// 在匹配图中寻找增广路径
if (!mp[x] || mp[x].length !== m + 1) return false; // 检查mp[x]是否定义且长度正确
for (let j = 1; j <= m; j++) {
if (mp[x][j] && chw[j]) {
chw[j] = false;
if (match[j] === 0 || findMuniu(match[j], mp, chw, match)) {
match[j] = x;
return true;
}
}
}
return false;
}
四.代码讲解(Java&Python&C++&JS分别讲解)
Python题解代码解析:
- 导入
itertools库中的combinations模块。 - 定义
find_min_kth_largest函数，接受矩阵和K作为参数。 - 获取矩阵的行数和列数。
- 使用
combinations生成所有包含N列的组合（N为矩阵的行数）。 - 遍历所有组合，对每个组合中的元素按降序排序，找到第K大的元素。
- 更新最小的第K大元素。
- 返回最小的第K大元素作为结果。
JAVA题解代码解析:
- 通过Scanner读取输入的N、M、K。
- 创建一个二维数组
matrix来存储输入的矩阵。 - 调用
findCombinations方法生成所有可能的组合，然后对每个组合中的元素进行排序。 - 将排序后的第K大的元素添加到结果集合中。
- 对结果集合进行排序，并输出排序后的第K大元素。
C/C++题解代码解析:
- 通过
cin读取输入的N、M、K。 - 创建一个二维数组
matrix来存储输入的矩阵。 - 调用
dfs方法生成所有可能的组合，然后对每个组合中的元素进行排序。 - 将排序后的第K大的元素添加到结果向量
ans中。 - 对
ans进行排序，并输出排序后的第K大元素。
JS题解代码解析:
- 使用Node.js中的readline模块逐行读取输入。
- 解析输入的行数、列数、和K值。
- 构建一个二维数组
myMap存储输入的矩阵。 - 使用二分查找法找到第K大的值，调用
check函数进行判断。 - 在
check函数中，构建匹配图，进行匈牙利匹配，判断是否存在至少n-K+1个匹配。 - 输出二分查找的结果。