Tutorial JAVA
Arquivo Java

Introdução

O problema de encontrar a mediana de duas matrizes classificadas é uma questão clássica de entrevista de codificação. O desafio é encontrar a mediana de forma eficiente, com uma complexidade de tempo de O(log(min(m, n))), onde m e n são os tamanhos das duas matrizes. Neste artigo, examinaremos uma solução Java que emprega pesquisa binária para alcançar essa eficiência.

Declaração do problema

Dadas duas matrizes classificadas nums1 e nums2, encontre a mediana das duas matrizes classificadas. A complexidade geral do tempo de execução deve ser O(log(min(m, n))), onde m e n são os tamanhos das duas matrizes.

Abordagem

Para resolver este problema, usamos uma abordagem de pesquisa binária no menor dos dois arrays. O objetivo é particionar ambas as matrizes de forma que a metade esquerda contenha todos os elementos menores ou iguais aos elementos da metade direita. Aqui está uma explicação passo a passo:

1. Certifique-se de que nums1 seja o array menor: Para uma pesquisa binária mais fácil, certifique-se de que nums1 seja o array menor.
2. Executar pesquisa binária: Use a pesquisa binária em nums1 para encontrar a partição correta.
3. Particionamento: particione ambos os arrays de forma que o lado esquerdo contenha elementos inferiores e o lado direito contenha elementos superiores.
4. Calcular mediana: com base nas partições, calcule a mediana.

Solução

Aqui está uma implementação Java detalhada da solução:

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
    }
}

Explicação

1. Inicialização: certifique-se de que nums1 seja o array menor.
2. Pesquisa binária: Execute uma pesquisa binária em nums1 para encontrar a partição correta.
3. Particionamento e cálculo da mediana: Calcule o máximo dos elementos da esquerda e o mínimo dos elementos da direita para encontrar a mediana.

Conclusão

Esta abordagem de pesquisa binária fornece uma solução eficiente para encontrar a mediana de duas matrizes classificadas. Ao aproveitar a pesquisa binária no array menor, a solução atinge uma complexidade de tempo de O(log(min(m, n))), tornando-a adequada para grandes arrays de entrada.