Mencari Median Dua Tatasusunan Diisih di Jawa

Tutorial JAVA
Fail Java

pengenalan

Masalah mencari median dua tatasusunan yang disusun 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 yang diisih. Kerumitan keseluruhan masa jalan 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 adalah penjelasan langkah demi langkah:

1. Pastikan nums1 ialah Array yang Lebih Kecil: Untuk carian binari yang lebih mudah, pastikan nums1 ialah array 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 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. Initialization: Pastikan nums1 ialah array 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.

以上是Mencari Median Dua Tatasusunan Diisih di Jawa的详细内容。更多信息请关注PHP中文网其他相关文章！