এই সমস্যায়, আমাদেরকে একটি 2D অ্যারে ম্যাট [r][c] দেওয়া হয়েছে যার উপাদানগুলি সাজানো হয়েছে৷ আমাদের কাজ হল সারি অনুসারে সাজানো ম্যাট্রিক্সে মধ্যমা খুঁজে বের করা।
বর্ণনা − আমাদের ম্যাট্রিক্সের উপাদানগুলির মধ্যক খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
mat = {
{2, 4, 7},
{5, 6, 8},
{4, 8, 9}
} আউটপুট
6
ব্যাখ্যা
অ্যারেতে সংরক্ষিত ম্যাট্রিক্সের উপাদানগুলি হল &মাইনাস
{2, 4, 4, 5, 6, 7, 8, 8, 9}
The median is 6. সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল অ্যারের সমস্ত উপাদান সংরক্ষণ করে। তারপর অ্যারে সাজানোর মাধ্যমে মধ্যম উপাদান খুঁজে বের করা।
সমস্যাটির আরও কার্যকরী সমাধান হল ম্যাট্রিক্সে সঠিক (r*c)/2টি ছোট এলিমেন্ট আছে তা ব্যবহার করে মধ্যম উপাদান খুঁজে বের করা। এবং আমরা অ্যারেতে উপাদানটি খুঁজে পাব যা এই শর্ত অনুসরণ করে। এর জন্য আমরা ম্যাট্রিক্সের সবচেয়ে ছোট এবং বৃহত্তম উপাদানটি নিয়ে ম্যাট্রিক্সে বাইনারি অনুসন্ধান ব্যবহার করব এবং তারপরে আমরা পরিসরের মাঝখানে খুঁজে বের করব এবং এতে ছোট উপাদানগুলির সংখ্যা পরীক্ষা করব। যদি এটি r*c/2 এর সমান হয় তাহলে সংখ্যাটি ফেরত দিন। যদি এটি (r*c)/2-এর থেকে বড় হয়, তাহলে আমরা সবচেয়ে বড় উপাদানটিকে মধ্যম পাওয়া থেকে ছোট উপাদানে পরিবর্তন করব এবং সংখ্যাটি (r*c)/2-এর থেকে ছোট হলে সবচেয়ে ছোটের জন্য একই কাজ করব।
মধ্যম উপাদানের চেয়ে ছোট উপাদানের গণনা, আমরা হয় মধ্যম থেকে বড় প্রথম উপাদানটির সূচী খুঁজে বের করে সারি অনুসারে সমস্ত উপাদান গণনা করতে পারি বা কেবলমাত্র উপরের_বাউন্ড ব্যবহার করতে পারি যা c++ এ একটি অন্তর্নির্মিত ফাংশন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
#define c 3
#define r 3
int findMedian(int mat[][c]) {
int smallest = INT_MAX, largest = INT_MIN;
for (int i=0; i<r; i++) {
if (mat[i][0] < smallest)
smallest = mat[i][0];
if (mat[i][c-1] > largest)
largest = mat[i][c-1];
}
while (smallest < largest){
int mid = smallest + (largest - smallest) / 2;
int smallCount = 0;
for (int i = 0; i < r; ++i)
smallCount += upper_bound(mat[i], mat[i]+c, mid) -
mat[i];
if (smallCount < ( (r * c + 1) / 2 ))
smallest = mid + 1;
else
largest = mid;
}
return smallest;
}
int main(){
int mat[][c]= { {2, 5, 7}, {4, 6, 8}, {1, 8, 9} };
cout<<"The median of the matrix is "<<findMedian(mat);
return 0;
} আউটপুট
The median of the matrix is 6
