সমস্যা বিবরণ
একই আকারের দুটি অ্যারে A[] এবং B[] দেওয়া আছে। কাজ হল একই আকারের একটি তৃতীয় অ্যারে তৈরি করা। রেজাল্ট অ্যারেতে দুটি অ্যারের মধ্যে থেকে সর্বোচ্চ n উপাদান থাকবে। এতে A[]-এর বাছাই করা উপাদানগুলো প্রথমে থাকবে, তারপর B[]-এর বাছাই করা উপাদানগুলো মূল অ্যারেতে যেসব ক্রমে ছিল সেসব ক্রমে থাকবে। যদি সাধারণ উপাদান থাকে তবে শুধু একটি উপাদান res[]-এ থাকবে এবং অগ্রাধিকার A[]-কে দেওয়া হবে।
উদাহরণ
যদি ইনপুট অ্যারেগুলো হয়:
arr1[] = {9, 17, 2, 25, 6}
arr2[] = {17, 4, 8, 10, 1}
তাহলে ফাইনাল অ্যারে: {9, 17, 25, 8, 10}
দ্রষ্টব্য: উপাদান ১৭ সাধারণ এবং অগ্রাধিকার arr1-কে দেওয়া হয়েছে।
অ্যালগরিদম
- দুটি অ্যারের কপি তৈরি করুন এবং সেগুলো ডিসেন্ডিং ক্রমে সর্ট করুন।
- হ্যাশ ব্যবহার করে দুটি অ্যারের নিরপেক্ষ n সর্বোচ্চ উপাদান বাছাই করুন, arr1[]-কে অগ্রাধিকার দিয়ে।
- রেজাল্ট অ্যারে খালি আরম্ভ করুন।
- arr1[] ট্রভার্স করুন, arr1[]-এর যেসব উপাদান হ্যাশে আছে সেগুলো কপি করুন। এটি উপাদানগুলোর ক্রম রক্ষা করার জন্য।
- ধাপ ৪ arr2[]-র জন্য दुহরান। এইবার শুধু যেসব উপাদান arr1[]-এ নেই সেগুলো বিবেচনা করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void printArray(vector<int>& arr, int n) {
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
void getMaxArray(int* arr1, int* arr2, int n) {
vector<int> temp1(arr1, arr1 + n);
vector<int> temp2(arr2, arr2 + n);
sort(temp1.begin(), temp1.end(), greater<int>());
sort(temp2.begin(), temp2.end(), greater<int>());
unordered_map<int, int> m;
int i = 0, j = 0;
while (m.size() < n) {
if (temp1[i] >= temp2[j]) {
m[temp1[i]]++;
++i;
} else {
m[temp2[j]]++;
++j;
}
}
vector<int> result;
for (int i = 0; i < n; ++i) {
if (m.find(arr1[i]) != m.end()) {
result.push_back(arr1[i]);
}
}
for (int i = 0; i < n; ++i) {
if (m.find(arr2[i]) != m.end() && m[arr2[i]] == 1) {
result.push_back(arr2[i]);
}
}
cout << "Final array:\n";
printArray(result, n);
}
int main() {
int arr1[] = {9, 17, 2, 25, 6};
int arr2[] = {17, 4, 8, 10, 1};
int n = sizeof(arr1) / sizeof(arr1[0]);
getMaxArray(arr1, arr2, n);
return 0;
}
আউটপুট
Final array: 9 17 25 8 10
