Ermitteln des Medians zweier sortierter Arrays in Java

JAVA-Tutorial
Java-Datei

Einführung

Das Problem, den Median zweier sortierter Arrays zu finden, ist eine klassische Frage in Codierungsinterviews. Die Herausforderung besteht darin, den Median effizient mit einer Zeitkomplexität von O(log(min(m, n))) zu finden, wobei m und n die Größen der beiden Arrays sind. In diesem Artikel gehen wir eine Java-Lösung durch, die eine binäre Suche verwendet, um diese Effizienz zu erreichen.

Problemstellung

Bestimmen Sie anhand zweier sortierter Arrays nums1 und nums2 den Median der beiden sortierten Arrays. Die gesamte Laufzeitkomplexität sollte O(log(min(m, n))) betragen, wobei m und n die Größen der beiden Arrays sind.

Ansatz

Um dieses Problem zu lösen, verwenden wir einen binären Suchansatz für das kleinere der beiden Arrays. Das Ziel besteht darin, beide Arrays so zu unterteilen, dass die linke Hälfte alle Elemente enthält, die kleiner oder gleich den Elementen in der rechten Hälfte sind. Hier ist eine Schritt-für-Schritt-Erklärung:

1. Stellen Sie sicher, dass nums1 das kleinere Array ist: Stellen Sie für eine einfachere binäre Suche sicher, dass nums1 das kleinere Array ist.
2. Binäre Suche durchführen: Verwenden Sie die binäre Suche auf nums1, um die richtige Partition zu finden.
3. Partitionierung: Partitionieren Sie beide Arrays so, dass die linke Seite niedrigere Elemente und die rechte Seite höhere Elemente enthält.
4. Median berechnen: Berechnen Sie basierend auf den Partitionen den Median.

Lösung

Hier ist eine detaillierte Java-Implementierung der Lösung:

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

Erläuterung

1. Initialisierung: Stellen Sie sicher, dass nums1 das kleinere Array ist.
2. Binäre Suche: Führen Sie eine binäre Suche auf nums1 durch, um die richtige Partition zu finden.
3. Partitionierung und Medianberechnung: Berechnen Sie das Maximum der linken Elemente und das Minimum der rechten Elemente, um den Median zu ermitteln.

Abschluss

Dieser binäre Suchansatz bietet eine effiziente Lösung zum Ermitteln des Medians zweier sortierter Arrays. Durch die Nutzung der binären Suche auf dem kleineren Array erreicht die Lösung eine Zeitkomplexität von O(log(min(m, n))), wodurch sie für große Eingabearrays geeignet ist.

Das obige ist der detaillierte Inhalt vonErmitteln des Medians zweier sortierter Arrays in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!