在 Java 中尋找兩個排序數組的中位數

JAVA教學
Java 檔案

介紹

求兩個排序數組的中位數的問題是一個經典的程式設計面試問題。挑戰在於有效地找出中位數，時間複雜度為 O(log(min(m, n)))，其中 m 和 n 是兩個陣列的大小。在本文中，我們將介紹一個使用二分搜尋來實現這種效率的 Java 解決方案。

問題陳述

給定兩個排序數組 nums1 和 nums2，找出這兩個排序數組的中位數。整體運行時複雜度應為 O(log(min(m, n)))，其中 m 和 n 是兩個陣列的大小。

方法

為了解決這個問題，我們對兩個數組中較小的一個使用二分搜尋方法。目標是對兩個陣列進行分區，使左半部包含小於或等於右半部元素的所有元素。以下是逐步說明：

1. 確保 nums1 是較小的陣列：為了更容易進行二分查找，請確保 nums1 是較小的陣列。
2. 執行二分查找：對 nums1 使用二分查找來找到正確的分區。
3. 分區：對兩個陣列進行分區，使左側包含較低的元素，右側包含較高的元素。
4. 計算中位數：根據分區，計算中位數。

解決方案

這是此解決方案的詳細 Java 實作：

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

解釋

1. 初始化：確保nums1是較小的陣列。
2. 二分查找：對nums1執行二分查找以找到正確的分區。
3. 分割和中位數計算：計算左側元素的最大值和右側元素的最小值，以求中位數。

結論

這種二分搜尋方法提供了一個有效的解決方案來找出兩個排序數組的中位數。透過在較小的數組上利用二分搜索，該解決方案實現了 O(log(min(m, n))) 的時間複雜度，使其適合大型輸入數組。

以上是在 Java 中尋找兩個排序數組的中位數的詳細內容。更多資訊請關注PHP中文網其他相關文章！