算法设计：在按行排序的矩阵中找到中位数

本文概述

• 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)个数字小于该数字。因此, 我们尝试找到少于所有数字的数字计数。以下是此方法的分步算法：

算法

:

1. 首先, 我们在矩阵中找到最小和最大元素。可以通过比较每行的第一个元素轻松找到最小元素, 类似地, 可以通过比较每行的最后一个元素找到最大元素。
2. 然后, 我们对从最小值到最大值的数字范围进行二进制搜索, 找到最小值和最大值的中位数, 并得到少于中位数的数字计数。并相应地更改最小值或最大值。
3. 为了使数字中位数, 应该有比该数字小(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 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

# 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

C#

// 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 give  the 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

输出如下：

Median is 5