Mencari Median Dua Tatasusunan Diisih di Jawa

Tutorial JAVA
Fail Java

pengenalan

Masalah mencari median dua tatasusunan yang diisih ialah soalan temu bual pengekodan klasik. Cabarannya ialah untuk mencari median dengan cekap, dengan kerumitan masa O(log(min(m, n))), di mana m dan n ialah saiz dua tatasusunan. Dalam artikel ini, kami akan menelusuri penyelesaian Java yang menggunakan carian binari untuk mencapai kecekapan ini.

Pernyataan Masalah

Diberi dua tatasusunan diisih nums1 dan nums2, cari median dua tatasusunan diisih. Kerumitan masa jalan keseluruhan hendaklah O(log(min(m, n))), dengan m dan n ialah saiz dua tatasusunan.

Pendekatan

Untuk menyelesaikan masalah ini, kami menggunakan pendekatan carian binari pada yang lebih kecil daripada dua tatasusunan. Matlamatnya adalah untuk membahagikan kedua-dua tatasusunan supaya separuh kiri mengandungi semua elemen kurang daripada atau sama dengan elemen dalam separuh kanan. Berikut ialah penjelasan langkah demi langkah:

1. Pastikan nums1 ialah Tatasusunan Lebih Kecil: Untuk carian binari yang lebih mudah, pastikan nums1 ialah tatasusunan yang lebih kecil.
2. Lakukan Carian Binari: Gunakan carian binari pada nums1 untuk mencari partition yang betul.
3. Pembahagian: Bahagikan kedua-dua tatasusunan supaya bahagian kiri mengandungi elemen yang lebih rendah dan bahagian kanan mengandungi elemen yang lebih tinggi.
4. Kira Median: Berdasarkan partition, hitung median.

Penyelesaian

Berikut ialah pelaksanaan Java terperinci bagi penyelesaian:

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

Penjelasan

1. Permulaan: Pastikan nums1 ialah tatasusunan yang lebih kecil.
2. Carian Binari: Lakukan carian binari pada nums1 untuk mencari partition yang betul.
3. Pembahagian dan Pengiraan Median: Kira maksimum unsur kiri dan minimum unsur kanan untuk mencari median.

Kesimpulan

Pendekatan carian binari ini menyediakan penyelesaian yang cekap untuk mencari median dua tatasusunan yang disusun. Dengan memanfaatkan carian binari pada tatasusunan yang lebih kecil, penyelesaian itu mencapai kerumitan masa O(log(min(m, n))), menjadikannya sesuai untuk tatasusunan input yang besar.

Atas ialah kandungan terperinci Mencari Median Dua Tatasusunan Diisih di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!