দুটি অ্যারে, A এবং B, এই টিউটোরিয়ালে আমাদের দেওয়া হয়েছে। উদাহরণ স্বরূপ, আমাদেরকে A-এর যেকোনো পারমুটেশন আউটপুট করতে হবে যাতে A[I ]> B[ I ] সূচকগুলি সর্বাধিক করা হয়, উদাহরণস্বরূপ
Input: A = [12, 22, 41, 13], B = [1, 20, 10, 12] Output: 12, 22, 41, 13 Input: A = [2, 5, 9, 7], B = [1, 12, 4, 54] Output: 2 7 5 9 Multiple answers can be present in that case we are simply going to print any one of the answers.
এই সমস্যায়, আমাদের সূচকগুলি সর্বাধিক করতে হবে যেখানে A[ i ]> B[ i ], তাই আমরা লোভের সাথে এই সমস্যাটি সমাধান করতে যাচ্ছি৷
সমাধান খোঁজার পদ্ধতি
এই পদ্ধতিতে, আমরা প্রথমে এখন উভয় অ্যারে বাছাই করব; আমরা অ্যারের B এর প্রতিটি সূচকের জন্য লোভের সাথে পরীক্ষা করি যাতে A[ i ] এর চেয়ে বেশি তাৎপর্যপূর্ণ এবং তারপর সেই উপাদানটিকে একটি ভেক্টরে রাখি।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int main(){
int A[] = { 2, 5, 9, 7 };
int B[] = { 1, 12, 4, 54 };
int n = sizeof(A) / sizeof(int); // size of our arrays
vector<pair<int, int> > A_pair, B_pair;
/***********************We are linking element to its position***********/
for (int i = 0; i < n; i++)
A_pair.push_back({A[i], i});
for (int i = 0; i < n; i++)
B_pair.push_back({B[i], i});
/***********************************************************************/
/*****Sorting our pair vectors********************/
sort(A_pair.begin(), A_pair.end());
sort(B_pair.begin(), B_pair.end());
int i = 0, j = 0, ans[n];
memset(ans, -1, sizeof(ans)); // initializing all the elements with value -1
vector<int> remaining; // this will store our elements which have lesser value than elemnt present in B.
while (i < n && j < n) {
// as our array is sorted then if we find any element in
//current index which has less value than B of current index then
// automatically it will have less value than other elements of B
// that's why we push such indices in remaining otherwise we push element in ans
if (A_pair[i].first > B_pair[j].first) {
ans[B_pair[j].second] = A_pair[i].first;
i++;
j++;
}
else {
remaining.push_back(i);
i++;
}
}
j = 0;
for (int i = 0; i < n; ++i){
// now if any index of answer is unchanged so that means
//we need to fill that position with the remaining elements
if (ans[i] == -1){
ans[i] = A_pair[remaining[j]].first;
j++;
}
}
for (int i = 0; i < n; i++) // printing our answer
cout << ans[i] << " ";
return 0;
} আউটপুট
2 7 5 9
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা প্রথমে সমস্ত উপাদানকে তাদের সূচকের সাথে লিঙ্ক করি যাতে আমরা এটি সাজানোর সময় তাদের পুরানো সূচকটি এখনও এটিতে থাকে। আমরা জোড়ার উভয় ভেক্টর বাছাই করি এখন আমরা লোভের সাথে আমাদের উত্তরগুলি অনুসন্ধান করি যখন আমরা উভয় অ্যারের মধ্য দিয়ে চলে যাই যদি আমরা A_pair-এর একটি সূচক পাই যার মান B_pair-এর চেয়ে বেশি চমৎকার, তাই আমরা সেটিকে আমাদের একটি অ্যারেতে (এবং B_pair এর অবস্থান) অন্যথায় আমরা উভয় ভেক্টরকে সাজিয়েছি, তাই আমরা জানি যে আমরা A_pair-এর এই মানটি ব্যবহার করতে পারব না, তাই আমরা সেই উপাদান সূচীটিকে আমাদের অবশিষ্ট ভেক্টরে পুশ করি এখন আমরা অবশিষ্টের সাহায্যে অ্যারে পূরণ করি। ভেক্টর, এবং তারপর আমরা উত্তর প্রিন্ট করি।
উপসংহার
এই টিউটোরিয়ালে, আমরা অন্য অ্যারের থেকে ছোট মান সহ একটি অ্যারের পারমুটেশন খুঁজে পেতে একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং আমরা যে সম্পূর্ণ পদ্ধতির সমাধান করেছি তাও শিখেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
