ধরুন আমাদের দুটি সাজানো অ্যারে রয়েছে 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 নামে একটি ম্যাট্রিক্স তৈরি করুন
- আমি 0 থেকে n – 1
- পরিসরে
- সারিতে ডেটা হিসাবে (A1[i], A2[0], 0) সন্নিবেশ করান
- যখন সারি খালি নয়, এবং k 0 নয়, তারপর
- curr :=সারির শীর্ষ, সারির উপাদান মুছুন
- curr-এর first_val, ret-এ curr-এর দ্বিতীয়_ভাল যোগ করুন
- যদি curr + 1
- সারিতে (curr এর প্রথম_ভাল, A2[curr + 1 এর সূচক], curr + 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,],]
