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

本篇文章分享华为OD机试C卷-- 矩阵匹配（Java & JS & Python & C），对你有帮助的话记得收藏一下，看Java资料网收获更多编程知识

获取题库不需要订阅专栏，可直接私信我进入CSDN领军人物top1博主的华为OD交流圈观看完整题库、最新面试实况、考试报告等内容以及大佬一对一答疑。
题目描述
从一个 N * M（N ≤ M）的矩阵中选出 N 个数，任意两个数字不能在同一行或同一列，求选出来的 N 个数中第 K 大的数字的最小值是多少。

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

输入格式：

N M K
N*M矩阵

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

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

题目解析
本题要求从给定的 N * M 矩阵中选出 N 个数，且这 N 个数不能在同一行或同一列。我们需要找到这些组合中第 K 大的数的最小值。由于题目要求“无需考虑重复数字，直接取字典排序结果即可”，我们可以理解为要求找到一种选数方式，使得剩余未选的数尽可能大，从而使得选出的数中第 K 大的数尽可能小。

这个问题可以转化为二分查找与贪心策略的结合。我们可以先确定第 K 大的数的可能范围，然后使用二分查找在这个范围内不断尝试可能的值。对于每个尝试的值 mid，我们使用贪心策略检查是否存在一种选数方式，使得选出的数中第 K 大的数恰好为 mid。

Java算法源码

文章来源:https://blog.csdn.net/wbajsjhhhhh/article/details/139399334
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！