算法设计（在按行排序的矩阵中找到中位数） _数据结构

本文概述

C ++
Java
Python3
C#

给定大小为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))中找到中值元素, 也可以使用讨论的方法
这里
在O(r * c)中找到中位数。在两种情况下, 所需的辅助空间均为O(r * c)。
An
有效的方法
对于这个问题是使用
二进制搜索
算法。这个想法是, 要使一个数字成为中位数, 应该有确切的(n / 2)个数字小于该数字。因此, 我们尝试找到少于所有数字的数字计数。以下是此方法的分步算法：
算法
:

首先, 我们在矩阵中找到最小和最大元素。可以通过比较每行的第一个元素轻松找到最小元素, 类似地, 可以通过比较每行的最后一个元素找到最大元素。
然后, 我们对从最小值到最大值的数字范围进行二进制搜索, 找到最小值和最大值的中位数, 并得到少于中位数的数字计数。并相应地更改最小值或最大值。
为了使数字中位数, 应该有比该数字小(r * c)/ 2个数字。因此, 对于每个数字, 我们通过在矩阵的每一行中使用upper_bound()来获得小于该数字的计数, 如果小于所需计数, 则中位数必须大于所选数字, 否则中位数必须为小于或等于所选数字。

下面是上述方法的实现：
C ++

// 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 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 givethe 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

# 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 ) / / 2while (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

// C# program to find median // of a matrix sorted row wise using System; class MedianInRowSorted{ // Function to find median // in the matrix static int binaryMedian( int [, ]m, int r, int c) { int max = int .MinValue; int min = int .MaxValue; 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 = Array.BinarySearch( GetRow(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 givethe number of // elements smaller than the number // including the searched element. else { while ( get < GetRow(m, i).GetLength(0) & & m[i, get ] == mid) get += 1; } place = place + get ; } if (place < desired) min = mid + 1; else max = mid; } return min; } public static int [] GetRow( int [, ] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int [rowLength]; for ( var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; }// Driver code public static void Main(String[] args) { int r = 3, c = 3; int [, ]m = {{1, 3, 5}, {2, 6, 9}, {3, 6, 9} }; Console.WriteLine( "Median is " + binaryMedian(m, r, c)); } } // This code is contributed by Princi Singh

输出如下：