দুটি সর্টেড অ্যারে A1, A2 এবং k দেওয়া। (u,v) পেয়ার যেখানে u∈A1, v∈A2। সবচেয়ে ছোট সমের k টি পেয়ার বের করতে হবে।
উদাহরণ: A1=[1,7,11], A2=[2,4,6], k=3 → [(1,2),(1,4),(1,6)]।
সমাধানের ধাপসমূহ
- মিন-হিপ (প্রায়োরিটি কিউ) ব্যবহার করুন।
- প্রথমে A1-এর প্রতিটি উপাদানের সাথে A2[0] পেয়ার পুশ করুন (সাম, u, v, idx)।
- k বার: টপ পপ করুন আউটপুটে যোগ করুন, তারপর সেটি অ্যারে-২-এর নেক্সট ইন্ডেক্স দিয়ে পুশ করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Data { int u, v, idx; Data(int a,int b,int c):u(a),v(b),idx(c) {} };
struct Cmp { bool operator()(Data a, Data b) { return a.u + a.v > b.u + b.v; } };
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& A1, vector<int>& A2, int k) {
priority_queue<Data, vector<Data>, Cmp> pq;
int n = A1.size(), m = A2.size();
if (!n || !m) return {};
for (int i = 0; i < n; i++) pq.push(Data(A1[i], A2[0], 0));
vector<vector<int>> ret;
while (!pq.empty() && k--) {
Data cur = pq.top(); pq.pop();
ret.push_back({cur.u, cur.v});
if (cur.idx + 1 < m) pq.push(Data(cur.u, A2[cur.idx+1], cur.idx+1));
}
return ret;
}
};
int main() {
vector<int> A1 = {1,7,11}, A2 = {2,4,6};
Solution ob;
auto res = ob.kSmallestPairs(A1, A2, 3);
for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
}
ইনপুট
[1,7,11] [2,4,6] 3
আউটপুট
[[1,2],[1,4],[1,6]]
