4. Median of Two Sorted Arrays

Leetcode

https://leetcode.com/problems/median-of-two-sorted-arrays/

題目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

解題

1. 時間複雜度需為 O(log (m+n)) => 二分搜尋法

2. 將兩個矩陣做 Partition，$p1 + p2 = pTotal = (m+n+1) / 2$ (一半的元素數量)

3. 如何找出 p1, p2，保證右邊的元素一定都比左邊的大 ? 邊界條件為 nums1[p1 - 1] <= nums2[p2] && nums2[p2 - 1] <= nums1[p1]

解答

解法 1

var findMedianSortedArrays = function(nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    const pTotal = Math.floor((m + n + 1) / 2);
    
    // 處理最前及最後元素的邊界狀況
    nums1[-1] = Number.MIN_SAFE_INTEGER;
    nums1[m] = Number.MAX_SAFE_INTEGER;
    nums2[-1] = Number.MIN_SAFE_INTEGER;
    nums2[n] = Number.MAX_SAFE_INTEGER;

    let low = 0;
    let high = m;
    while (low <= high) {
        const p1 = Math.floor((low + high) / 2);
        const p2 = pTotal - p1;
        if (nums1[p1 - 1] <= nums2[p2] && nums2[p2 - 1] <= nums1[p1]) {
            const isEven = (m+n) % 2 === 0
            if (isEven) {
                const left = Math.max(nums1[p1 - 1], nums2[p2 - 1]);
                const right = Math.min(nums1[p1], nums2[p2]);
                return (left + right) / 2;
            } else {
                return Math.max(nums1[p1 - 1], nums2[p2 - 1]);
            }
        }
        // 如果 nums1 的長度比較長，p2 計算出來有可能是負的
        if (nums1[p1 - 1] > nums2[p2] || p2 < 0) {
            high = p1 - 1;
            continue;
        }
        if (nums2[p2 - 1] > nums1[p1] || p2 > n) {
            low = p1 + 1;
            continue;
        }
    }
};

解法二 (以長度較短的矩陣進行二分搜尋)

var findMedianSortedArrays = function(nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    
    // 保證 nums1 的長度比較短
    if (m>n) return findMedianSortedArrays(nums2, nums1);
    const pTotal = Math.floor((m + n + 1) / 2);
    
    nums1[-1] = Number.MIN_SAFE_INTEGER;
    nums1[m] = Number.MAX_SAFE_INTEGER;
    nums2[-1] = Number.MIN_SAFE_INTEGER;
    nums2[n] = Number.MAX_SAFE_INTEGER;

    let low = 0;
    let high = m;
    while (low <= high) {
        const p1 = Math.floor((low + high) / 2);
        const p2 = pTotal - p1;
        if (nums1[p1 - 1] <= nums2[p2] && nums2[p2 - 1] <= nums1[p1]) {
            const isEven = (m+n) % 2 === 0
            if (isEven) {
                const left = Math.max(nums1[p1 - 1], nums2[p2 - 1]);
                const right = Math.min(nums1[p1], nums2[p2]);
                return (left + right) / 2;
            } else {
                return Math.max(nums1[p1 - 1], nums2[p2 - 1]);
            }
        }
        // 不用考慮 p2 為負的狀況
        if (nums1[p1 - 1] > nums2[p2]) {
            high = p1 - 1;
            continue;
        }
        if (nums2[p2 - 1] > nums1[p1]) {
            low = p1 + 1;
            continue;
        }
    }
};

測資

let nums1 = [1,2], nums2 = [3,4];
nums1 = [23,26,31,35], nums2 = [3,5,7,9,11,16];
nums1 = [1,3], nums2 = [2];
nums1 = [6], nums2 = [1,2,3,4,5,7,8,9,10];
nums1 = [1,2], nums2 = [3,4,5,6,7,8,9,10];

參考資料

• https://www.youtube.com/watch?v=LPFhl65R7ww