004 Median of Two Sorted Arrays[H]

02-03

1 題目描述

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)).

難度：Hard

2 題目樣例

Example 1:nnums1 = [1, 3]nnums2 = [2]nnThe median is 2.0nnExample 2:nnums1 = [1, 2]nnums2 = [3, 4]nnThe median is (2 + 3)/2 = 2.5n

3 題意分析

給出兩個排序後的序列nums1和nums2，讓求兩個序列合併後序列的中位數，要求在 $O(lg(n+m))$ 的時間內完成。

4 思路分析

1 歸併

如果不限制複雜度的話非常簡單，兩個數組一合併排序下就出來了，複雜度是 $O(klgk)$ ，其中 $k=m+n$ 。

看到這個題的時候，我第一反應就是歸併。

只要歸併前 $frac {m+n-1} {2}$ 項就可以得到中位數，不過為了讓空間複雜度降低到 $O(1)$ 我這裡用了點小技巧，就是假設兩個數組相應的迭代器為 $it1$ 和 $it2$ ，然後一個迭代器 $it$ 每次循環 $it=min(it1,it2)$ ，然後如果 $*it1<*it2$ 就it1++，反之it2++，最後 $it$ 的位置就是中位數的位置。總體思想還是歸併，但是空間複雜度可以降低。

代碼如下

class Solution {npublic:n double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {n int len = nums1.size() + nums2.size();n auto it1 = nums1.begin();n auto it2 = nums2.begin();n vector<int>::iterator it;n int count = 0;n int next;n while(count <= (len-1)/2){n count++;n if(it1 == nums1.end()){n it = it2;n it2++;n continue;n }n if(it2 == nums2.end()){n it = it1;n it1 ++;n continue;n }n if(*it1 < *it2){n it = it1;n it1++;n }n else{n it = it2;n it2 ++;n }n }n if(len&1)n return *it;n else{n if(it1 == nums1.end())n next = *it2;n else if(it2 == nums2.end())n next = *it1;n elsen next = min(*it1, *it2);n return (double)(*it + next)/2;n }n }n};n

演算法時間複雜度 $O(m+n)$ ，空間複雜度 $O(1)$ ，但是加入輸入掛後速度實際上超過了99.3%的代碼，好像也挺快的（

2 二分

首先考慮中位數的性質，如果一個序列被中位數分成兩個子序列，那麼其中一個子序列中的元素一定都小於或等於另一個子序列的元素。

按照這個定義，我們假設輸入的序列為A和B，長度分別為m和n，並且m<n，那麼我們可以在A和B中分別尋找一個i和j使得

$max (A[0]...A[i-1],B[0],...B[j-1]) le min(A[i]...A[m-1],B[j]...B[n-1]) i +j =m - i + n-j$

那麼我們可以得到中位數就是

$median =frac { max (A[0]...A[i-1],B[0],...B[j-1]) + min(A[i]...A[m-1],B[j]...B[n-1]) } {2}$

考慮到A和B都是已經排序的，我們只要

$A[i-1] le B[j] B[j-1] le A[i]$

並且對於每一個i有

$j=frac {m+n+1} {2} - i$

即可滿足之前中位數的定義，這樣的話我們只要在序列A中二分搜索i即可。

代碼實現如下（直接摘自Leetcode）

class Solution {npublic:ntdouble findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {nttint n = nums1.size(), m = nums2.size();nttif (n > m) {ntttswap(n, m);ntttswap(nums1, nums2);ntt}nttint l, r, mid, pos, id = (n + m + 1) / 2;nttl = 0, r = n;nttwhile (l <= r)ntt{ntttmid = (l + r) >> 1;ntttpos = id - mid;ntttif (mid < n && nums2[pos - 1] > nums1[mid]) l = mid + 1;ntttelse if (mid >= 1 && nums2[pos] < nums1[mid - 1]) r = mid - 1;ntttelse break;ntt}nttdouble ans;nttif (mid == 0) ans = nums2[pos - 1];nttelse if (pos == 0) ans = nums1[mid - 1];nttelse ans = max(nums1[mid - 1], nums2[pos - 1]);nttif ((n + m) & 1) return ans;nttelsentt{ntttif (mid == n) ans = (ans + nums2[pos]) / 2.0;ntttelse if (pos == m) ans = (ans + nums1[mid]) / 2.0;ntttelse ans = (ans + min(nums1[mid], nums2[pos])) / 2.0;ntt}nttreturn ans;nt}n};n

演算法時間複雜度為 $O(lg(min(m,n)))$ ，空間複雜度 $O(1)$ ，在LeetCode上跑出了最快成績15ms，比上面歸併的33ms好了不少。

5 後記

好題，二分的做法可以說是把A和B有序的性質利用的淋漓盡致了。