在按行排序的矩阵中找到中位数
原文： 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))中找到中值元素，也可以使用这里讨论的方法在O(r * c)中找到中值。 在两种情况下，所需的辅助空间均为O(r * c)。
解决此问题的有效方法**是使用二分搜索算法。 这个想法是，要使一个数成为中位数，应有准确的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 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
Output:
Median is 5
时间复杂度：O(32 * r * log(c))。 上限函数将花费log(c)时间，并针对每一行执行。 并且由于数字的最大值为 32 位，因此从最小值到最大值的二分搜索将最多执行 32（log2(2 ^ 32) = 32）个操作。
辅助空间：O(1)。
版权属于：月萌API www.moonapi.com，转载请注明出处
