135 views
C++ Program for Find k pairs with Smallest Sums in Two Arrays
To find k pairs with the smallest sums in two arrays in C++, you can use a priority queue (min-heap). You’ll create pairs from the two arrays, calculate their sums, and keep track of the k smallest sums using the priority queue. Here’s a C++ program to do that:
C++
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int, int>> result;
if (nums1.empty() || nums2.empty() || k <= 0) {
return result;
}
auto compare = [&](pair<int, int>& a, pair<int, int>& b) {
return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> min_heap(compare);
// Start with pairs (0, 0), (1, 0), ..., (k-1, 0) if possible
for (int i = 0; i < min(k, static_cast<int>(nums1.size())); i++) {
min_heap.emplace(i, 0);
}
while (k-- > 0 && !min_heap.empty()) {
auto idx_pair = min_heap.top();
min_heap.pop();
int i = idx_pair.first;
int j = idx_pair.second;
result.emplace_back(nums1[i], nums2[j]);
// Add the next pair (i, j+1) if j+1 is within bounds
if (j + 1 < nums2.size()) {
min_heap.emplace(i, j + 1);
}
}
return result;
}
int main() {
vector<int> nums1 = {1, 7, 11};
vector<int> nums2 = {2, 4, 6};
int k = 3;
vector<pair<int, int>> result = kSmallestPairs(nums1, nums2, k);
cout << "K pairs with smallest sums: " << endl;
for (const auto& pair : result) {
cout << "(" << pair.first << ", " << pair.second << ") ";
}
cout << endl;
return 0;
}In this program:
- The
kSmallestPairsfunction takes two input arraysnums1andnums2, as well as an integerkrepresenting the number of pairs to find. - We use a priority queue (
min_heap) to store pairs, where each pair consists of indices(i, j)fromnums1andnums2, respectively. - We define a custom comparison function (
compare) that compares pairs based on their sum. - We start with pairs
(0, 0),(1, 0), …,(k-1, 0)if possible, pushing them into the priority queue. - In each iteration, we pop the pair with the smallest sum from the priority queue, add it to the result vector, and consider the next pair
(i, j+1)ifj+1is within bounds. - Finally, we return the
ksmallest pairs found.
This program will find and print the k pairs with the smallest sums from the two input arrays nums1 and nums2.