এই সমস্যায়, আমাদের একটি ২D অ্যারে mat[r][c] দেওয়া আছে যearen উপাদানগুলো সারি অনুযায়ী সাজানো। আমাদের কাজ হলো সারি অনুযায়ী সাজানো ম্যাট্রিক্সে মেডিয়ান খুঁজে বের করা।
বিবরণ
আমাদের ম্যাট্রিক্সের সব উপাদানের মেডিয়ান বের করতে হবে।
উদাহরণ
ইনপুট
mat = {
{2, 4, 7},
{5, 6, 8},
{4, 8, 9}
}
আউটপুট
6
ব্যাখ্যা
ম্যাট্রিক্সের উপাদানগুলো অ্যারেতে সংরক্ষণ করলে পাই:
{2, 4, 4, 5, 6, 7, 8, 8, 9} মেডিয়ান হলো 6।
সমাধানের পদ্ধতি
একটি সহজ সমাধান হলো সব উপাদানগুলো একটা অ্যারেতে সংরক্ষণ করে সেটি সাজিয়ে মেডিয়ান বের করা।
একটি আরও কার্যকর সমাধান হলো এই তথ্য ব্যবহার করে যে মেডিয়ান এলিমেন্টের ঠিক (r*c)/2 ছোট উপাদান ম্যাট্রিক্সে থাকে। আমরা বাইনারি সার্চ ব্যবহার করব ম্যাট্রিক্সের সবচেয়ে ছোট এবং বড় উপাদান নিয়ে, তারপর মাঝপথের এলিমেন্ট বের করে তার চেয়ে ছোট কতগুলো এলিমেন্ট আছে সেটি চেক করব। যদি সেটি (r*c)/2-র সমান হয়, তবে সেই নম্বরটি ফেরত দিব। যদি বেশি হয়, তবে সবচেয়ে বড় এলিমেন্ট কমিয়ে দিব, আর যদি কম হয় তবে সবচেয়ে ছোট এলিমেন্ট বাড়িয়ে দিব।
মাঝপথের এলিমেন্টের চেয়ে ছোট উপাদান সংখ্যা বের করতে আমরা অপার বাউন্ড (upper_bound) ফাংশন ব্যবহার করতে পারি যা C++-তে বিল্ট-ইন।
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 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
