[LeetCode] #4 Median of Two Sorted Arrays

Problem

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

Solution

這題若直接運用 Merge Sort 的概念可順利通過所有測資，Time Complexity 為 O(m+n)

Runtime: 144 ms, faster than 99.47% of C# online submissions for Median of Two Sorted Arrays.
Memory Usage: 25.7 MB, less than 48.96% of C# online submissions for Median of Two Sorted Arrays.

但仔細一看發現案情並不單純，題目有規定 Time Complexity 至少要在 O(log(m+n)) 才算是真正解題，所以這題其實還蠻難的，參考了討論區，才知道得運用 Binary Search 的觀念，這邊分享一部我覺得很棒的教學影片，內有非常詳細的解說

其概念大致是，我們將兩組數列 A 及 B 分別以 i 及 j 切割成左半邊與右半邊

        Left            |         Right
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]

將兩組數列合併，我們希望能滿足兩個條件

1. 左半邊的總長度 = 右半邊的總長度
2. 左半邊的最大值 < 右半邊的最小值

如果滿足，我們就可以計算出 Median = (max(Left) + min(Right)) / 2，而要確保兩個條件都滿足，那就要再分別滿足

1. i + j
   = m - i + n - j (總長度為偶數) 或是
   = m - i + n - j + 1 (總長度為奇數)，但其實可採後者，因為後續計算時皆取整數，加不加 1 並不影響結果，所以可推得 j = (m + n + 1) / 2 - i
2. B[j - 1] ≤ A[i] 及 A[i - 1] ≤ B[j]

因此當 B[j - 1] > A[i]，代表 i 切割得太左邊，我們得將 i 的值往右調整，而 j 自然會往左調整；當 A[i - 1] > B[j]，代表 i 切割得太右邊，得將 i 的值往左調整，而 j 自然會往右調整。至於 i 要用什麼方式去切最有效率？這邊就要採用 Binary Search，不斷地去將檢查範圍縮小

1. 令 iMin= 0, iMax= m
2. 以 [iMin, iMax] 區間開始搜尋
3. i = (iMin + iMax) / 2
4. 欲將 i 值往右逼近，則將 iMin + 1；欲將 i 值往左逼近，則將 iMax - 1

只要掌握上述所有邏輯，最終就可以順利找出 Median，此寫法 Time Complexity 可以到 O(log(min(m, n))) 比題目規定的還更有效率；Space Complexity 則為 O(1)

Runtime: 128 ms, faster than 100.00% of C# online submissions for Median of Two Sorted Arrays.
Memory Usage: 25.7 MB, less than 75.00% of C# online submissions for Median of Two Sorted Arrays.

原題網址
Median of Two Sorted Arrays

參考資料
leetCode_4_Median_of_Two_Sorted_Arrays