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:
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
Método simple : el método más simple para resolver este problema es almacenar todos los elementos de la array dada en una array de tamaño r*c. Luego, podemos ordenar la array y encontrar el elemento mediano en O(r*clog(r*c)) o podemos usar el enfoque discutido aquí para encontrar la mediana en O(r*c). El espacio auxiliar requerido será O(r*c) en ambos casos.
Un enfoque eficiente para este problema es utilizar un algoritmo de búsqueda binaria . La idea es que para que un número sea la mediana debe haber exactamente (n/2) números que sean menores que este número. Entonces, tratamos de encontrar el conteo de números menor que todos los números. A continuación se muestra el algoritmo paso a paso para este enfoque:
Algoritmo :
- Primero, encontramos los elementos mínimo y máximo en la array. El elemento mínimo se puede encontrar fácilmente comparando el primer elemento de cada fila y, de manera similar, el elemento máximo se puede encontrar comparando el último elemento de cada fila.
- Luego usamos la búsqueda binaria en nuestro rango de números de mínimo a máximo, encontramos la mitad del mínimo y el máximo y obtenemos un conteo de números menor que nuestra mitad. Y en consecuencia cambiar el mínimo o máximo.
- Para que un número sea la mediana, debe haber (r*c)/2 números más pequeños que ese número. Entonces, para cada número, obtenemos el conteo de números menores que usando upper_bound() en cada fila de la array, si es menor que el conteo requerido, la mediana debe ser mayor que el número seleccionado, de lo contrario, la mediana debe ser menor o igual al número seleccionado.
A continuación se muestra la implementación del enfoque anterior:
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
Producción:
Median is 5
Complejidad temporal : O(32 * r * log(c)). La función de límite superior tomará el tiempo log(c) y se realiza para cada fila. Y dado que los números tendrán un máximo de 32 bits, la búsqueda binaria de números de mínimo a máximo se realizará en un máximo de 32 operaciones (log2(2^32) = 32).
Espacio Auxiliar : O(1)
Consulte el artículo completo sobre Encontrar la mediana en la array ordenada por filas para obtener más detalles.
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