資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中查詢K對最小和
假設我們有兩個已排序的陣列A1和A2，以及另一個值k。我們必須定義一個對(u, v)，它由A1中的一個元素和A2中的另一個元素組成。我們必須找到k個這樣的對，例如[(u1, v1), (u2, v2),…, (uk, vk)]。因此，如果A1 = [1, 7, 11]且A2 = [2, 4, 6]，k = 3，則輸出將為[(1, 2), (1, 4), (1, 6)]
為了解決這個問題，我們將遵循以下步驟：
- 定義一種資料型別，它將包含兩個值a和b，以及索引。
- 建立一個優先佇列，它將採用資料型別的鍵和資料的列表作為值。
- n := A1的大小，m := A2的大小
- 如果n為0或m為0，則返回。
- 建立一個名為ret的矩陣。
- 對於範圍從0到n-1的i
- 將(A1[i], A2[0], 0)作為資料插入佇列。
- 當佇列不為空且k不為0時
- curr := 佇列的頂部，刪除佇列元素。
- 將curr的第一個值和第二個值插入ret。
- 如果curr的索引+1 < m，則
- 將資料(curr的第一個值, A2[curr的索引+1], curr的索引+1)插入佇列。
- k減1。
- 返回ret。
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
#include <stack>
using namespace std;
struct Data{
int firstVal, secondVal, idx;
Data(int a, int b, int c){
firstVal = a;
secondVal = b;
idx = c;
}
};
struct Comparator{
bool operator()(Data a, Data b){
return !(a.firstVal + a.secondVal < b.firstVal + b.secondVal);
}
};
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue <Data, vector <Data>, Comparator> pq;
int n = nums1.size();
int m = nums2.size();
if(!n || !m)return {};
vector < vector <int> > ret;
for(int i = 0; i < n; i++){
pq.push(Data(nums1[i], nums2[0], 0));
}
while(!pq.empty() && k--){
Data curr = pq.top();
pq.pop();
ret.push_back({curr.firstVal, curr.secondVal});
if(curr.idx + 1 < m){
pq.push(Data(curr.firstVal, nums2[curr.idx + 1], curr.idx + 1));
}
}
return ret;
}
};
void print(vector <int> const &arr) {
cout<<"[";
for(int i=0; i < arr.size(); i++)
std::cout << arr.at(i) <<",";
cout<<"]";
}
int main() {
vector<int> nums1{1,7,11};
vector<int> nums2{2,4,6};
int k = 3;
Solution ob1;
vector<vector<int>> numsRet;
numsRet = ob1.kSmallestPairs(nums1, nums2, k);
cout<<"[";
for (vector<int> x : numsRet) {
print(x);
cout<<",";
}
cout<<"]"<<endl;
return 0;
}輸入
[1,7,11]
[2,4,6]
3
vector<int> nums1{1,7,11};
vector<int> nums2{2,4,6};
int k = 3;
Solution ob1;
vector<vector<int>> numsRet;
numsRet = ob1.kSmallestPairs(nums1, nums2, k);輸出
[[1,2,],[1,4,],[1,6,],]
更新於：2020年4月29日
143 次瀏覽
廣告