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 है, तो वापस लौटें
• रिट नामक एक मैट्रिक्स बनाएं
• मैं के लिए 0 से n - 1 की सीमा में
  • डेटा के रूप में कतार में डालें (A1[i], A2[0], 0)
• जबकि कतार खाली नहीं है, और k 0 नहीं है, तब
  • curr :=कतार में सबसे ऊपर, कतार तत्व हटाएं
  • कर्र का पहला_वैल, रिट में दूसरा_वल डालें
  • यदि curr + 1
  • कतार में (कर्र का पहला_वल, ए2 [कर का इंडेक्स + 1], कर्व का इंडेक्स + 1) के साथ डेटा डालें
• k को 1 से घटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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,],]