在 C++ 中查找总和最小的 K 对
c++server side programmingprogramming
假设我们有两个排序数组 A1 和 A2，以及另一个值 k。我们必须定义一个对 (u, v)，它由来自 A1 的一个元素和来自 A2 的另一个元素组成。我们必须找到像 [(u1, v1), (u2, v2),…, (uk, vk)] 这样的 k 对。因此，如果 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 的矩阵
- 对于 i，范围为 0 到 n – 1
- 将 (A1[i], A2[0], 0) 作为数据插入队列
- 当队列不为空，且 k 不为 0 时，则
- curr := 队列顶部，删除队列元素
- 将 curr 的 first_val、curr 的 second_val 插入 ret
- 如果 curr 的索引 + 1 < m，则
- 将 (curr 的 first_val、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,],]
