Tìm K cặp có tổng nhỏ nhất trong C ++

Giả sử chúng ta có hai mảng đã sắp xếp A1 và A2, và một giá trị khác k. Chúng ta phải xác định một cặp (u, v) bao gồm một phần tử từ A1 và một phần tử khác từ A2. Chúng ta phải tìm k cặp như [(u1, v1), (u2, v2),…, (uk, vk)]. Vì vậy, nếu A1 =[1, 7, 11] và A2 =[2, 4, 6] và k =3, thì đầu ra sẽ là [(1, 2), (1, 4), (1, 6)]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một kiểu dữ liệu, kiểu dữ liệu này sẽ nhận hai giá trị a và b và lập chỉ mục.
• tạo một hàng đợi ưu tiên, hàng đợi này sẽ lấy khóa của loại dữ liệu và danh sách dữ liệu làm giá trị.
• n:=kích thước của A1, m:=kích thước của A2
• nếu n là 0 hoặc m là 0, thì trả về
• tạo một ma trận được gọi là ret
• cho tôi trong phạm vi từ 0 đến n - 1
  • chèn (A1 [i], A2 [0], 0) dưới dạng dữ liệu vào hàng đợi
• hàng đợi while không trống và k không phải 0, thì
  • curr:=đầu hàng đợi, xóa phần tử hàng đợi
  • chèn first_val of curr, second_val of curr vào ret
  • nếu chỉ mục của curr + 1
  • chèn dữ liệu với (first_val of curr, A2 [index of curr + 1], index of curr + 1), vào hàng đợi
• giảm k đi 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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;
}

Đầu vào

[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);

Đầu ra

[[1,2,],[1,4,],[1,6,],]