Tutorial JAVA
Archivo Java

Introducción

El problema de encontrar la mediana de dos matrices ordenadas es una pregunta clásica de una entrevista de codificación. El desafío es encontrar la mediana de manera eficiente, con una complejidad temporal de O (log (min (m, n))), donde myn son los tamaños de las dos matrices. En este artículo, analizaremos una solución Java que emplea búsqueda binaria para lograr esta eficiencia.

Planteamiento del problema

Dadas dos matrices ordenadas nums1 y nums2, encuentre la mediana de las dos matrices ordenadas. La complejidad general del tiempo de ejecución debe ser O(log(min(m, n))), donde myn son los tamaños de las dos matrices.

Acercarse

Para resolver este problema, utilizamos un enfoque de búsqueda binaria en la más pequeña de las dos matrices. El objetivo es dividir ambas matrices de modo que la mitad izquierda contenga todos los elementos menores o iguales que los elementos de la mitad derecha. Aquí tienes una explicación paso a paso:

1. Asegúrese de que nums1 sea la matriz más pequeña: para una búsqueda binaria más sencilla, asegúrese de que nums1 sea la matriz más pequeña.
2. Realizar búsqueda binaria: utilice la búsqueda binaria en nums1 para encontrar la partición correcta.
3. Particionado: particiona ambas matrices de manera que el lado izquierdo contenga elementos inferiores y el lado derecho contenga elementos superiores.
4. Calcular mediana: según las particiones, calcula la mediana.

Solución

Aquí hay una implementación Java detallada de la solución:

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0, high = x;

        while (low  minY) {
                high = partitionX - 1;
            } else {
                low = partitionX   1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted");
    }

    public static void main(String[] args) {
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();

        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median: "   solution.findMedianSortedArrays(nums1, nums2)); // Output: 2.0

        int[] nums1_2 = {1, 2};
        int[] nums2_2 = {3, 4};
        System.out.println("Median: "   solution.findMedianSortedArrays(nums1_2, nums2_2)); // Output: 2.5
    }
}

Explicación

1. Inicialización: asegúrese de que nums1 sea la matriz más pequeña.
2. Búsqueda binaria: realiza una búsqueda binaria en nums1 para encontrar la partición correcta.
3. Partición y cálculo de la mediana: Calcula el máximo de los elementos izquierdos y el mínimo de los elementos derechos para encontrar la mediana.

Conclusión

Este enfoque de búsqueda binaria proporciona una solución eficiente para encontrar la mediana de dos matrices ordenadas. Al aprovechar la búsqueda binaria en la matriz más pequeña, la solución logra una complejidad temporal de O(log(min(m, n))), lo que la hace adecuada para matrices de entrada grandes.