इस समस्या में, हमें एक 2D सरणी mat[r][c] दी गई है जिसके तत्व पंक्ति-वार क्रमबद्ध हैं। हमारा कार्य पंक्ति-वार क्रमबद्ध मैट्रिक्स में माध्यिका ज्ञात करना है।
विवरण - हमें मैट्रिक्स के तत्वों की माध्यिका ज्ञात करनी है।
आइए एक उदाहरण से समझते हैं:
इनपुट
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 के बराबर है तो संख्या लौटाएँ। यदि यह (r*c)/2 से अधिक है, तो सबसे बड़े तत्व को मध्य से छोटे तत्व में बदलें और वही सबसे छोटे के लिए करें यदि गिनती (r*c)/2 से कम है।
मध्य तत्व से छोटे तत्वों की गिनती, हम या तो सभी तत्वों को पंक्ति-वार गिन सकते हैं मध्य से बड़े पहले तत्व का इंडेक्स खोजकर या सरलता से upper_bound का उपयोग कर सकते हैं जो 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
