用C ++查找带排序行的矩阵的Kth最小和

假设我们有一个m*n矩阵，称为mat，一个整数k，mat的行以非降序排列。我们可以从每一行中精确选择一个元素来形成一个数组。我们必须在所有可能的数组中找到第K个最小的数组和。

因此，如果输入像mat=[[1,3,11]，[2,4,6]]

1

3

1

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