一. 題目-矩陣匹配
從一個NM（N<=M)的矩陣中選出N個數(shù)，任意兩個數(shù)字不能在同一行或同一列，求選出來的N個數(shù)中第K大的數(shù)字的最小值是多少。
輸入描述：
輸入矩陣要求：1<=K<=N<=M<=150
輸入格式：N M K
NM矩陣
輸出描述：
N*M的矩陣中可以選出M!/N!種組合數(shù)組，每個組合數(shù)組中第K大的數(shù)中的最小值。無需考慮重復(fù)數(shù)字，直接取字典排序結(jié)果即可。
補(bǔ)充說明：注意：結(jié)果是第K大的數(shù)字的最小值
示例1
輸入：3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
輸出：3
說明：N*M的矩陣中可以選出M!/N!種組合數(shù)組，每個組合數(shù)組中第K大的數(shù)中的最小值；上述輸入中選出的數(shù)組組合為1,3,6; 1,3,3; 1,4,8; 1,4,3;…上述輸入樣例中選出的組合數(shù)組有24種，最小數(shù)組為1,3,3，則2大的最小值為3
二.解題思路
-
生成所有包含N個數(shù)字的組合：文章來源：http://www.zghlxwxcb.cn/news/detail-848675.html
- 使用itertools.combinations或其他方法從給定的矩陣中生成所有包含N個數(shù)字的可能組合。
-
計算每個組合中第K大的元素：文章來源地址http://www.zghlxwxcb.cn/news/detail-848675.html
- 對于每個生成的組合，按降序?qū)?shù)字進(jìn)行排序并選擇第K個元素。這就是該組合中第K大的元素。
到了這里，關(guān)于矩陣匹配【華為OD機(jī)試JAVA&Python&C++&JS題解】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
