Trouver la médiane de deux tableaux triés en Java

Tutoriel JAVA
Fichier Java

Introduction

Le problème de trouver la médiane de deux tableaux triés est une question classique d'entretien de codage. Le défi est de trouver efficacement la médiane, avec une complexité temporelle de O(log(min(m, n))), où m et n sont les tailles des deux tableaux. Dans cet article, nous présenterons une solution Java qui utilise la recherche binaire pour atteindre cette efficacité.

Énoncé du problème

Étant donné deux tableaux triés nums1 et nums2, trouvez la médiane des deux tableaux triés. La complexité globale d'exécution doit être O(log(min(m, n))), où m et n sont les tailles des deux tableaux.

Approche

Pour résoudre ce problème, nous utilisons une approche de recherche binaire sur le plus petit des deux tableaux. Le but est de partitionner les deux tableaux de telle sorte que la moitié gauche contienne tous les éléments inférieurs ou égaux aux éléments de la moitié droite. Voici une explication étape par étape :

1. Assurez-vous que nums1 est le plus petit tableau : Pour une recherche binaire plus facile, assurez-vous que nums1 est le plus petit tableau.
2. Effectuer une recherche binaire : utilisez la recherche binaire sur nums1 pour trouver la partition correcte.
3. Partitionnement : partitionnez les deux tableaux de telle sorte que le côté gauche contienne des éléments inférieurs et que le côté droit contienne des éléments supérieurs.
4. Calculer la médiane : En fonction des partitions, calculez la médiane.

Solution

Voici une implémentation Java détaillée de la solution :

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 <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            // Edge cases
            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxX <= minY && maxY <= minX) {
                // Correct partition
                if ((x + y) % 2 == 0) {
                    return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
                } else {
                    return Math.max(maxX, maxY);
                }
            } else if (maxX > 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
    }
}

Explication

1. Initialisation : assurez-vous que nums1 est le plus petit tableau.
2. Recherche binaire : effectuez une recherche binaire sur nums1 pour trouver la partition correcte.
3. Partitionnement et calcul de la médiane : Calculez le maximum des éléments de gauche et le minimum des éléments de droite pour trouver la médiane.

Conclusion

Cette approche de recherche binaire fournit une solution efficace pour trouver la médiane de deux tableaux triés. En tirant parti de la recherche binaire sur le plus petit tableau, la solution atteint une complexité temporelle de O(log(min(m, n))), ce qui la rend adaptée aux grands tableaux d'entrée.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!