[LeetCode] 4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

• Hardness: \(\color{red}\textsf{Hard}\)
• Ralated Topics: Array、Binary Search、Divide and Conquer

一、題目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the sorted arrays.
The overall run time complexity should be O(log (m+n)).

Example 1:

• Input: nums1 = [1,3], nums2 = [2]
• Output: 2.00000
• Explanation: merged array = [1,2,3] and median is 2.

Example 2:

• Input: nums1 = [1,2], nums2 = [3,4]
• Output: 2.50000
• Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• -10^6 <= nums1[i], nums2[i] <= 10^6

二、分析

• 這題用暴力解，先兩個數組合併後再求值，其時間複雜度為 \(O(m+n)\)。不符合題目要求。
• 因為兩個數組為已排序的數組，故我們可以利用其性質：
  • nums1 中第 k 個元素表示有 k-1 個數比它還小。
• 故我們可以用分治法去處理這個問題，
  • 求第 kth 個元素。
  • 若 nums1 中前 3 個數確定小於 median 值，則我們可以視為求第 k-3 個數
  • \(\texttt{[1,2,3,3,4]}\) 求 9 個數中的第 5 小的數
    \(\text{}\uparrow\)
    \(\texttt{[2,4,6,8]}\)
    \(\text{}\uparrow\)
  • \(\texttt{[1,2,3,3,4]}\) 求剩下 6 個數中的第 2 小的數
    \(\text{　　　}\uparrow\)
    \(\texttt{[2,4,6,8]}\)
    \(\text{}\uparrow\)
  • 如此一來，我們每次可以逼進 Median 的個數為 log(m)或 log(n)，也就是說時間複雜度降為 \(O(\log(m+n))\)
• 或是我們也可以將 num1 與 nums2 各別分為兩個子數組，並以長度較小的數組來切(可以降低時間複雜度)。
  • \(\texttt{[1,2|3,4]}\)
    \(\texttt{[2,4|6,8,9]}\)
  • 其切割線左右的四個值 l1、l2、r1、r2 符合以下性質時可求得 median
    • l1 <= r2
    • l2 <= r1
    • 奇數時為 max(l1, l2)
    • 偶數時為 max(l1, l2) + min(r1,r2) 的平均

三、解題

1. Brute Method

• Time complexity: \(O(m+n)\)
• Space complexity: \(O(m+n)\)

double findMedianSortedArray(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = num2.size();
    vector<int> nums;       // 先將兩個數組 merge 後再求 median
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (nums1[i] < nums2[j])
            nums.push_back(nums1[i++]);
        else
            nums.push_back(nums2[j++]);
    }
    while (i < m) nums.push_back(nums1[i++]);
    while (j < n) nums.push_back(nums2[j++]);

    int len = nums.size();
    // 若數組長度為奇數則回傳中間的值，若為偶數則為中間兩數的平均。
    return (len & 1) ? (nums[len/2]/1.0) : (nums[len/2-1] + nums[len/2])/2.0;
}

2. Kth Element

• Time complexity: \(O(\log(m+n))\)
• Space complexity: \(O(1)\)

vector<int> nums1, nums2
int m, n;

// nums1 確定有 i 個元素小於 median，nums2 中確定有 j 個元素小於 median，求第 k 個元素
double kth(int i, int j, int k) {   
    if (i == m) return nums2[j+k-1];    // nums1 用完了，直接對 nums2 取第 j+k 個元素
    if (j == n) return nums1[i+k-1];    // nums2 用完了，直接對 nums1 取第 i+k 個元素
    if (k == 1) return min(nums1[i], nums2[j]); //當前比較小的即為第 k 個元素

    int mid1 = (i+k/2-1) >= m ? INT_MAX : nums1[i+k/2-1];
    int mid2= (i+k/2-1) >= n ? INT_MAX : unms2[j+k/2-1];

    // 兩個數組都往前推 k/2 個，其當前值較小的，其數組前 k/2 個數必定小於 median
    if (mid1 < mid2)
        return kth(i+k/2, j, k-k/2);
    else
        return kth(i, j+k/2, k-k/2);
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    this->nums1 = nums1;
    this->nums2 = nums2;
    this->m = nums1.size();
    this->n = nums2.size();
    int len = m + n;
    // 若數組長度為奇數則回傳中間的值，若為偶數則為中間兩數的平均。
    if (len & 1) return kth(0, 0, len/2+1)/1.0;
    return (kth(0, 0, len/2) + kth(0, 0, len/2+1))/2.0;
}

3. Binary Search

• Time complexity: \(O(\log(\text{min}(m+n)))\)
• Space complexity: \(O(1)\)

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    int len = m + n;
    // 確保 nums1 的長度比較短，以減少時間複雜度
    if (m > n) return findMedianSortedArrays(nums2, nums1);
    int l = 0, r = m;
    int l1, l2, r1, r2;
    // binary search
    while (l <= r) {
        int cut1 = (l+r)/2;
        int cut2 = (len+1)/2 - cut1;    // 注意 len+1
        l1 = cut1 == 0 ? INT_MIN : nums1[cut1-1];
        l2 = cut2 == 0 ? INT_MIN : nums2[cut2-1];
        r1 = cut1 == m ? INT_MAX : nums1[cut1];
        r2 = cut2 == n ? INT_MAX : nums2[cut2];
        if (l1 <= r2 && l2 <= r1) {     // median 必定為 l1 或 l2
            break;
        } else if (l1 > r2) {
            r = cut1-1;
        } else {
            l = cut1+1;
        }
    }
    if (len & 1) return max(l1, l2)/1.0;
    return (max(l1, l2) + min(r1, r2))/2.0;
}

回目錄 Catalog