假设我们有一个m * n矩阵，称为mat，一个整数k，mat的行以非降序排列。我们可以从每一行中精确选择一个元素来形成一个数组。我们必须在所有可能的数组中找到第K个最小的数组和。
因此，如果输入像mat = [[1,3,11]，[2,4,6]]
1 | 3 | 1 |
| 2 | 4 | 6 |
并且k = 5，则输出将为7，因为当我们从每行中选择一个元素时，前k个最小的和为[1,2]，[1,4]，[3,2]，[3,4] ，[1,6]。第五个总和是7。
为了解决这个问题，我们将遵循以下步骤-
定义一个优先级队列pq
定义一个2D数组m
定义一个函数update()，它将使用数组v，i，好的，用false初始化它，
如果i与v的大小相同，则-
sum：= sum + m [j，v [j]]
返回
如果ok为假，则-
返回
对于初始化j：= 0，当j <v的大小时，更新（将j增加1），执行-
定义一个数组临时并将v复制到其中
在开始时将sum插入temp
将温度插入pq
返回
（将v [i]增加1）
如果ok为假且v [i] <z，则-
更新（v，i + 1，true）
更新（v，i + 1，true）
更新（v，i + 1，ok）
从主要方法中执行以下操作-
m：+给定矩阵
ret：= 0
n：= m的行数
z：= m的列数
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-
ret：= ret + m [i，0]
定义大小为n的数组温度
在开始时将ret插入temp
将温度插入pq
定义一组
当k为非零值时，请在每次迭代中将k减1，然后执行-
从pq中删除元素
定义一个数组temp = pq的顶部
从pq中删除元素
将temp插入s
ret：= temp [0]
从temp中删除temp的第一个元素
更新（温度，0）
而（不是pq为空，并且pq的顶部元素是s的成员），则执行-
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
struct Cmp{
bool operator()(vector <int>& a, vector <int>& b) {
return !(a[0] < b[0]);
}
};
class Solution {
public:
priority_queue<vector<int>, vector<vector<int> >, Cmp> pq;
vector<vector<int> > m;
int z;
void update(vector<int>& v, int i, bool ok = false){
if (i == v.size()) {
if (!ok)
return;
int sum = 0;
for (int j = 0; j < v.size(); j++) {
sum += m[j][v[j]];
}
vector<int> temp(v.begin(), v.end());
temp.insert(temp.begin(), sum);
pq.push(temp);
return;
}
v[i]++;
if (!ok && v[i] < z)
update(v, i + 1, true);
v[i]--;
update(v, i + 1, ok);
}
int kthSmallest(vector<vector<int> >& m, int k){
this->m = m;
int ret = 0;
int n = m.size();
z = m[0].size();
for (int i = 0; i < n; i++) {
ret += m[i][0];
}
vector<int> temp(n);
temp.insert(temp.begin(), ret);
pq.push(temp);
set<vector<int> > s;
while (k--) {
vector<int> temp = pq.top();
pq.pop();
s.insert(temp);
ret = temp[0];
temp.erase(temp.begin());
update(temp, 0);
while (!pq.empty() && s.count(pq.top())) {
pq.pop();
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,3,11},{2,4,6}};
cout << (ob.kthSmallest(v, 5));
}{{1,3,11},{2,4,6}}输出结果
7