मान लीजिए हमारे पास दो सॉर्ट की गई सरणी 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 नामक एक मैट्रिक्स बनाएं
- i को 0 से n-1 तक लूप करें
- (A1[i], A2[0], 0) को डेटा के रूप में क्यू में डालें
- जब तक क्यू खाली नहीं है, और k 0 नहीं है
- curr := क्यू का शीर्ष, क्यू तत्व हटाएं
- curr के first_val, 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
आउटपुट
[[1,2,],[1,4,],[1,6,],]
