在按行排序的矩阵中找到中位数 · GeeksForGeeks 中文系列教程

# 在按行排序的矩阵中找到中位数 > 原文： [https://www.geeksforgeeks.org/find-median-row-wise-sorted-matrix/](https://www.geeksforgeeks.org/find-median-row-wise-sorted-matrix/) 给定大小为 r * c 的按行排序的矩阵，我们需要找到给定矩阵的中位数。假定 r * c 总是奇数。例子： ``` Input : 1 3 5 2 6 9 3 6 9 Output : Median is 5 If we put all the values in a sorted array A[] = 1 2 3 3 5 6 6 9 9) Input: 1 3 4 2 5 6 7 8 9 Output: Median is 5 ``` **简单方法**：解决此问题的最简单方法是将给定矩阵的所有元素存储在大小为 r * c 的数组中。然后，我们可以对数组进行排序并在 O（r * clog（r * c））中找到中值元素，也可以使用此处讨论的[方法](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/)在 O（r * c）中找到中值。在两种情况下，所需的辅助空间均为 O（r * c）。解决此问题的有效方法**是使用[二分搜索](https://www.geeksforgeeks.org/binary-search/)算法。这个想法是，要使一个数成为中位数，应有准确的（n / 2）个数小于该数。因此，我们尝试找到少于所有数字的数字计数。以下是此方法的分步算法： **算法****： 1. 首先，我们在矩阵中找到最小和最大元素。可以通过比较每行的第一个元素轻松找到最小元素，类似地，可以通过比较每行的最后一个元素找到最大元素。 2. 然后，我们对从最小值到最大值的数字范围进行二分搜索，找到最小值和最大值的中位数，并得到小于中位数的数量计数。并相应地更改最小值或最大值。 3. 为了使数字中位数，应该有比该数字小（r * c）/ 2 个数字。因此，对于每个数字，我们通过在矩阵的每一行中使用 upper_bound（）来获得小于该数字的计数，如果小于所需计数，则中位数必须大于所选数字，否则中位数必须小于等于或等于所选数字。下面是上述方法的实现： ## C++ ```cpp // C++ program to find median of a matrix // sorted row wise #include<bits/stdc++.h> using namespace std; const int MAX = 100; // function to find median in the matrix int binaryMedian(int m[][MAX], int r ,int c) { int min = INT_MAX, max = INT_MIN; for (int i=0; i<r; i++) { // Finding the minimum element if (m[i][0] < min) min = m[i][0]; // Finding the maximum element if (m[i][c-1] > max) max = m[i][c-1]; } int desired = (r * c + 1) / 2; while (min < max) { int mid = min + (max - min) / 2; int place = 0; // Find count of elements smaller than mid for (int i = 0; i < r; ++i) place += upper_bound(m[i], m[i]+c, mid) - m[i]; if (place < desired) min = mid + 1; else max = mid; } return min; } // driver program to check above functions int main() { int r = 3, c = 3; int m[][MAX]= { {1,3,5}, {2,6,9}, {3,6,9} }; cout << "Median is " << binaryMedian(m, r, c) << endl; return 0; } ``` ## Java ```java // Java program to find median of a matrix // sorted row wise import java.util.Arrays; public class MedianInRowSorted { // function to find median in the matrix static int binaryMedian(int m[][],int r, int c) { int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i=0; i<r ; i++) { // Finding the minimum element if(m[i][0] < min) min = m[i][0]; // Finding the maximum element if(m[i][c-1] > max) max = m[i][c-1]; } int desired = (r * c + 1) / 2; while(min < max) { int mid = min + (max - min) / 2; int place = 0; int get = 0; // Find count of elements smaller than mid for(int i = 0; i < r; ++i) { get = Arrays.binarySearch(m[i],mid); // If element is not found in the array the // binarySearch() method returns // (-(insertion_point) - 1). So once we know // the insertion point we can find elements // Smaller than the searched element by the // following calculation if(get < 0) get = Math.abs(get) - 1; // If element is found in the array it returns // the index(any index in case of duplicate). So we go to last // index of element which will give the number of // elements smaller than the number including // the searched element. else { while(get < m[i].length && m[i][get] == mid) get += 1; } place = place + get; } if (place < desired) min = mid + 1; else max = mid; } return min; } // Driver Program to test above method. public static void main(String[] args) { int r = 3, c = 3; int m[][]= { {1,3,5}, {2,6,9}, {3,6,9} }; System.out.println("Median is " + binaryMedian(m, r, c)); } } // This code is contributed by Sumit Ghosh ``` ## Python3 ```py # Python program to find median of matrix # sorted row wise from bisect import bisect_right as upper_bound MAX = 100; # Function to find median in the matrix def binaryMedian(m, r, d): mi = m[0][0] mx = 0 for i in range(r): if m[i][0] < mi: mi = m[i][0] if m[i][d-1] > mx : mx = m[i][d-1] desired = (r * d + 1) // 2 while (mi < mx): mid = mi + (mx - mi) // 2 place = [0]; # Find count of elements smaller than mid for i in range(r): j = upper_bound(m[i], mid) place[0] = place[0] + j if place[0] < desired: mi = mid + 1 else: mx = mid print ("Median is", mi) return # Driver code r, d = 3, 3 m = [ [1, 3, 5], [2, 6, 9], [3, 6, 9]] binaryMedian(m, r, d) # This code is contributed by Sachin BIsht ``` Output: ``` Median is 5 ``` **时间复杂度**：O（32 * r * log（c））。上限函数将花费 log（c）时间，并针对每一行执行。并且由于数字的最大值为 32 位，因此从最小值到最大值的二分搜索将最多执行 32（log2（2 ^ 32）= 32）个操作。 **辅助空间**：`O(1)`