題目網址：https://leetcode.cn/problems/median-of-two-sorted-arrays/

題意：給兩個排序過的 array nums1 和 nums2, 其大小分別為 m 和 n, 返回這兩個 array 排序過的中位數。

設計 $O(log(m+n))$ time 的演算法。

Solution 1：

想法：利用 Binary Search, 我們可以用分隔線將兩個 sorted array 分割成兩邊, 而中位數只與紅線兩側的元素有關。因為是 sorted array, 所以我們用 Binary Search 找出正確的分割線位置, 需滿足以下條件：

  • 當 m + n 為偶數時, 紅線左邊的元素個素和右邊的元素個數相等。中位數為分割線左邊最大元素、分割線右邊最小元素之平均

  • 當 m + n 為奇數時, 紅線左邊的元素個素比右邊的元素個數多 1(這樣方便我們計算中位數)

    e.g. nums1 = [1], nums2 = [2, 3] ➔ 紅線左邊元素 = [1,2], 紅線右邊元素 = [3]

    ➔ 我們可直接取紅線左邊元素值最大的數為中位數

  • 紅線左邊元素的值 ≤ 紅線右邊元素的值, 也就是 nums1[cutA-1] ≤ nums2[cutB] && nums2[cutB-1] ≤ nums1[cutA]

分隔線的定義 :

  • cutA = nums1 分隔線右邊的第一個元素 idx = nums1 分隔線左邊的元素個數

  • cutB = nums2 分隔線右邊的第一個元素 idx = nums2 分隔線左邊的元素個數

  • 滿足 cutA + cutB = half = (m + n + 1) / 2

為什麼是選較短的 array 做 Binary Search, 而不是較長的 array ?

因為這樣時間複雜度比較低

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int m = nums1.size(), n = nums2.size();

        // 確保 m <= n
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }

        // 分割線左側的元素個數 = (m + n + 1) / 2
        const int half = m + (n - m + 1) / 2; // 避免 overflow 的寫法

        // 用 Binary Search 找出正確分割線的位置
        int left = 0, right = m;
        while (left < right) {
            const int cutA = left + (right - left) / 2; // 避免 overflow 的寫法
            const int cutB = half - cutA;

            // 代表 nums1 左邊元素太小, 因此往右邊繼續找
            if (nums1[cutA] < nums2[cutB - 1]) {
                left = cutA + 1;
            } else { // 代表 nums1 左邊元素太大, 因此往左邊繼續找
                right = cutA;
            }
        }

        // 得到正確分割線的位置
        const int cutA = left, cutB = half - cutA;

        // 左中位數 = 左側元素值最大的, 也就是 nums1[cutA-1] 和 nums2[cutB-1] 中取較大者
        // 若有超出邊界的, 則把它設成最小值, 這樣必然取沒超出邊界的
        const int leftMax = max((cutA == 0) ? INT_MIN : nums1[cutA - 1],
                                (cutB == 0) ? INT_MIN : nums2[cutB - 1]);

        // 若為奇數, 中位數即為分割線左邊元素值最大的數
        if ((m + n) % 2 == 1) {
            return leftMax;
        }

        // 右中位數 = 右側元素值最小的, 也就是 nums1[cutA] 和 nums2[cutB] 中取較小者
        // 若有超出邊界的, 則把它設成最大值, 這樣必然取沒超出邊界的
        const int rightMin = min((cutA == m) ? INT_MAX : nums1[cutA],
                                 (cutB == n) ? INT_MAX : nums2[cutB]);

        // 若為偶數, 中位數即為左中位數和右中位數之平均
        return leftMax * 0.5 + rightMin * 0.5; // 避免 overflow 的寫法
    }
};
  • time：$O(log(m))$ ➔ 對 nums1 做 Binary Search
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：同 Solution 1, 只是改變 nums1 做 Binary Search 的寫法, 判斷式改成 nums1[cutA - 1] > nums2[cutB], 但有邊界條件須考慮, 也就是當 nums1[cutA - 1] ≤ nums2[cutB] 時, 此時 left = cutA。若 nums1 中只有兩個元素, e.g. nums1 = [0, 1], 此時 left = 0, right = 1 ➔ cutA = 0, 更新完後的 left 仍為 0, 會導致陷入無窮迴圈中。因此要把計算 cutA 的公式改成 left + (right - left + 1) / 2, 新增 + 1 的部分是為了避免陷入無窮迴圈中

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int m = nums1.size(), n = nums2.size();

        // 確保 m <= n
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }

        // 分割線左側的元素個數 = (m + n + 1) / 2
        const int half = m + (n - m + 1) / 2; // 避免 overflow 的寫法

        // 用 Binary Search 找出正確分割線的位置
        int left = 0, right = m;
        while (left < right) {
            const int cutA = left + (right - left + 1) / 2; // + 1  是為了避免陷入無窮迴圈中
            const int cutB = half - cutA;

            // 代表 nums1 左邊元素太大, 因此往右邊繼續找
            if (nums1[cutA - 1] > nums2[cutB]) {
                right = cutA - 1;
            } else {
                // 代表 nums1 左邊元素太小, 因此往左邊繼續找
                // 當 nums1 只有兩個元素時會陷入無窮迴圈中
                left = cutA;
            }
        }

        // 得到正確分割線的位置
        const int cutA = left, cutB = half - cutA;

        // 左中位數 = 左側元素值最大的, 也就是 nums1[mid1-1] 和 nums2[mid2-1] 中取較大者
        const int leftMax = max((cutA == 0) ? INT_MIN : nums1[cutA - 1],
                                (cutB == 0) ? INT_MIN : nums2[cutB - 1]);

        // 若為奇數, 中位數即為分割線左邊元素值最大的數
        if ((m + n) % 2 == 1) {
            return leftMax;
        }

        // 右中位數 = 右側元素值最小的, 也就是 nums1[mid1] 和 nums2[mid2] 中取較小者
        const int rightMin = min((cutA == m) ? INT_MAX : nums1[cutA],
                                 (cutB == n) ? INT_MAX : nums2[cutB]);

        // 若為偶數, 中位數即為左中位數和右中位數之平均
        return leftMax * 0.5 + rightMin * 0.5; // 避免 overflow 的寫法
    }
};
  • time：$O(log(m))$ ➔ 對 nums1 做 Binary Search
  • space：$O(1)$ ➔ 只需常數空間