資料結構
網路
關係資料庫管理系統 (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 次檢視
