इस समस्या में, हमें एक 2D array mat[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 से छोटा है तो सबसे छोटे एलिमेंट के लिए भी ऐसा ही करेंगे।
मध्य तत्व से छोटे तत्वों की गिनती, हम या तो मध्य से बड़े पहले तत्व की अनुक्रमणिका ढूंढकर सभी तत्वों को पंक्ति-वार गिन सकते हैं या केवल ऊपरी_बाउंड का उपयोग कर सकते हैं जो सी ++ में एक इनबिल्ट फ़ंक्शन है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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