এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে, m আকারের অ্যারে ডেল[] এবং একটি পূর্ণসংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল প্রদত্ত উপাদানগুলি মুছে ফেলার পরে k ক্ষুদ্রতম সংখ্যাগুলি সন্ধান করা .
del[] অ্যারেতে উপস্থিত সমস্ত উপাদান মুছে ফেলার পরে পাওয়া অ্যারে অ্যারে থেকে আমাদের প্রথম k ক্ষুদ্রতম উপাদানগুলি প্রিন্ট করতে হবে। যদি অ্যারেতে দুটি দৃষ্টান্ত উপস্থিত থাকে তবে প্রথম দৃষ্টান্তটি মুছুন।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2 Output : 2, 5
ব্যাখ্যা −
Array arr[] after deleting the elements : {5, 7, 2} 2 minimum elements are 2, 5.
সমাধান পদ্ধতি
del[]-এ উপস্থিত arr[] থেকে সমস্ত উপাদান মুছে ফেলার মাধ্যমে সমস্যার একটি সহজ সমাধান। তারপর অ্যারেটিকে ক্রমবর্ধমান ক্রমে সাজান এবং অ্যারের প্রথম k উপাদান মুদ্রণ করুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h> using namespace std; void findKminElementDelArray(int arr[], int n, int del[], int m, int k){ for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(arr[j] == del[i]){ arr[j] = INT_MAX; break; } } } sort(arr, arr + n); for (int i = 0; i < k; ++i) { cout<<arr[i]<<" "; } } int main(){ int array[] = { 3, 5, 1, 7, 9, 2 }; int m = sizeof(array) / sizeof(array[0]); int del[] = { 1, 9, 3 }; int n = sizeof(del) / sizeof(del[0]); int k = 2; cout<<k<<" smallest numbers after deleting the elements are "; findKminElementDelArray(array, m, del, n, k); return 0; }
আউটপুট
2 smallest numbers after deleting the elements are 2 5
অন্য পদ্ধতি
সমস্যা সমাধানের আরেকটি পদ্ধতি হল হ্যাশম্যাপ এবং হিপ ব্যবহার করা। আমরা একটি মিন-হিপ এবং একটি হ্যাশ ম্যাপ তৈরি করব। হ্যাশম্যাপে অ্যারে del[]-এর সমস্ত উপাদান থাকবে। এবং তারপর অ্যারের অ্যারের উপাদানগুলি সন্নিবেশ করুন যা হ্যাশ-ম্যাপে মিন-হিপে উপস্থিত নেই। হিপ থেকে k উপাদানগুলি পপ করুন এবং তারপরে এটি মুদ্রণ করুন৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h> using namespace std; void findKminElementDelArray(int arr[], int n, int del[], int m, int k){ unordered_map<int, int> deleteElement; for (int i = 0; i < m; ++i) { deleteElement[del[i]]++; } priority_queue<int, vector<int>, greater<int> > minHeap; for (int i = 0; i < n; ++i) { if (deleteElement.find(arr[i]) != deleteElement.end()) { deleteElement[arr[i]]--; if (deleteElement[arr[i]] == 0) deleteElement.erase(arr[i]); } else minHeap.push(arr[i]); } for (int i = 0; i < k; ++i) { cout<<minHeap.top()<<" "; minHeap.pop(); } } int main(){ int array[] = { 3, 5, 1, 7, 9, 2 }; int m = sizeof(array) / sizeof(array[0]); int del[] = { 1, 9, 3 }; int n = sizeof(del) / sizeof(del[0]); int k = 2; cout<<k<<" smallest numbers after deleting the elements are "; findKminElementDelArray(array, m, del, n, k); return 0; }
আউটপুট
2 smallest numbers after deleting the elements are 2 5