Nos dan una array ordenada por filas de tamaño r*c, necesitamos encontrar la mediana de la array dada. Se supone que r*c siempre es impar.
Ejemplos:
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 or equal to 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] > max)
max = m[i];
}
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 or equal
// to 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 or equal to 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 or equal to 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
Javascript
<script>
// Javascript program to find median
// of a matrix sorted row wise
// Function to find median
// in the matrix
function binaryMedian(m, r, c)
{
var max = -1000000000;
var min = 1000000000;
for(var 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] > max)
max = m[i];
}
var desired = parseInt((r * c + 1) / 2);
while(min < max)
{
var mid = min + parseInt((max - min) / 2);
var place = 0;
var get = 0;
// Find count of elements
// smaller than or equal to mid
for(var i = 0; i < r; ++i)
{
var tmp = GetRow(m, i);
for(var j = tmp.length; j>=0; j--)
{
if(tmp[j] <= mid)
{
get = j+1;
break;
}
}
// 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).length &&
m[i][get] == mid)
get += 1;
}
place = place + get;
}
if (place < desired)
min = mid + 1;
else
max = mid;
}
return min;
}
function GetRow(matrix, row)
{
var rowLength = matrix[0].length;
var rowVector = Array(rowLength).fill(0);
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row][i];
return rowVector;
}
// Driver code
var r = 3, c = 3;
var m = [[1,3,5],
[2,6,9],
[3,6,9]];
document.write("Median is " +
binaryMedian(m, r, c));
// This code is contributed by rutvik_56.
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA