数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中查找已排序行的矩阵的第K小和
假设我们有一个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]。这里的第5个和是7。
为了解决这个问题，我们将遵循以下步骤：
定义一个优先级队列pq
定义一个二维数组m
定义一个函数update()，它将接收一个数组v，i，ok并将其初始化为false，
如果i与v的大小相同，则：
如果ok为false，则：
返回
返回
对于初始化j := 0，当j < v的大小时，更新（j递增1），执行：
sum := sum + m[j, v[j]]
定义一个数组temp并将v复制到其中
将sum插入到temp的开头
将temp插入到pq中
返回
（v[i]递增1）
如果ok为false且v[i] < z，则：
update(v, i + 1, true)
update(v, i + 1, true)
update(v, i + 1, ok)
从主方法执行以下操作：
m :+ 给定矩阵
ret := 0
n := m的行数
z := m的列数
对于初始化i := 0，当i < n时，更新（i递增1），执行：
ret := ret + m[i, 0]
定义一个大小为n的数组temp
将ret插入到temp的开头
将temp插入到pq中
定义一个集合s
当k不为零时，每次迭代k递减1，执行：
定义一个数组temp = pq的顶部元素
从pq中删除元素
将temp插入到s中
ret := temp[0]
从temp中删除temp的第一个元素
update(temp, 0)
当（pq不为空且pq的顶部元素是s的成员）时，执行：
从pq中删除元素
返回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
239 次查看
