4. Median of Two Sorted Arrays
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)).
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
思路
要求在給定的兩個有序數組中裡面找其中的中位數，硬性要求時間複雜度為 O(log(m+n)) O ( l o g ( m + n ) )
問題可以轉化為兩個有序序列找第num大的數，由于時間複雜度被限制死，是以不能采用排序後再找中位數的方法（時間複雜度高）。以下參考 兩個有序數組中的中位數和Top K問題
預備知識
先解釋下“割”
我們通過切一刀，能夠把有序數組分成左右兩個部分，切的那一刀就被稱為割(Cut)，割的左右會有兩個元素，分别是左邊最大值和右邊最小值。
我們定義L = Max(LeftPart)，R = Min(RightPart)
Ps. 割可以割在兩個數中間，也可以割在1個數上，如果割在一個數上，那麼這個數即屬于左邊，也屬于右邊。（後面講單數組中值問題的時候會說）
比如說[2 3 5 7]這個序列，割就在3和5之間
[2 3 / 5 7]
中值就是（3+5）/2 = 4
如果[2 3 4 5 6]這個序列，割在4上，我們可以把4分成2個
[2 3 (4/4) 5 7]
中值就是（4+4）/2 = 4
這樣可以保證不管中值是1個數還是2個數都能統一運算。
割和第k個元素
對于單數組，找其中的第k個元素特别好做，我們用割的思想就是：如果在k的位置割一下，A[k]屬于左邊部分的最大值。
雙數組
我們設:
Ci為第i個數組的割。
Li為第i個數組割後的左元素.
Ri為第i個數組割後的右元素。
如何從雙數組裡取出第k個元素
- 首先Li<=Ri是肯定的（因為數組有序，左邊肯定小于右邊）
- 如果我們讓L1<=R2 && L2<=R1
- 那麼左半邊 全小于右半邊，如果左邊的元素個數相加剛好等于k，那麼第k個元素就是Max(L1,L2)，參考上面常識1。
- 如果 L1>R2，說明數組1的左邊元素太大（多），我們把C1減小，把C2增大。L2>R1同理，把C1增大，C2減小。
假設k=3
對于
[1 4 7 9]
[2 3 5]
設C1 = 2，那麼C2 = k-C1 = 1
[1 4/7 9]
[2/3 5]
這時候，L1(4)>R2(3)，說明C1要減小，C2要增大，C1 = 1，C2=k-C1 = 2
[1/4 7 9]
[2 3/5]
這時候，滿足了L1<=R2 && L2<=R1，第3個元素就是Max(1,3) = 3。
如果對于上面的例子，把k改成4就恰好是中值。
下面具體來看特殊情況的中值問題。
雙數組的奇偶
中值的關鍵在于，如何處理奇偶性，單數組的情況，我們已經讨論過了，那雙數組的奇偶問題怎麼辦，m+n為奇偶處理方案都不同，
讓數組恒為奇數
有沒有辦法讓兩個數組長度相加一定為奇數或偶數呢？
其實有的，虛拟加入‘#’(這個trick在manacher算法中也有應用)，讓數組長度恒為奇數（2n+1恒為奇數）。
Ps.注意是虛拟加，其實根本沒這一步，因為通過下面的轉換，我們可以保證虛拟加後每個元素跟原來的元素一一對應
| 之前 | len | 之後 | len |
|---|---|---|---|
| [1 4 7 9] | 4 | [# 1 # 4 # 7 # 9 #] | 9 |
| [2 3 5] | 3 | [# 2 # 3 # 5 #] | 7 |
映射關系
這有什麼好處呢，為什麼這麼加?因為這麼加完之後，每個位置可以通過/2得到原來元素的位置。
| / | 原位置 | 新位置 | 除2後 |
|---|---|---|---|
| 1 | 1 | ||
| 5 | 2 | 5 | 2 |
在虛拟數組裡表示“割”
不僅如此，割更容易，如果割在‘#’上等于割在2個元素之間，割在數字上等于把數字劃到2個部分。
奇妙的是不管哪種情況：
Li = (Ci-1)/2
Ri = Ci/2
例：
- 割在4/7之間‘#’，C = 4，L=(4-1)/2=1 ，R=4/2=2
剛好是4和7的原來位置！
- 割在3上，C = 3，L=(3-1)/2=1，R=3/2 =1，剛好都是3的位置！
剩下的事情就好辦了，把2個數組看做一個虛拟的數組A，目前有2m+2n+2個元素，割在m+n+1處，是以我們隻需找到m+n+1位置的元素和m+n+2位置的元素就行了。
左邊：A[m+n+1] = Max(L1+L2)
右邊：A[m+n+2] = Min(R1+R2)
Mid = (A[m+n+1]+A[m+n+2])/2
= (Max(L1+L2) + Min(R1+R2) )/2
至于在兩個數組裡找割的方案，就是上面的方案。
分治的思路
有了上面的知識後，現在的問題就是如何利用分治的思想。
怎麼分？
最快的分的方案是二分，有2個數組，我們對哪個做二分呢？
根據之前的分析，我們知道了，隻要C1或C2确定，另外一個也就确定了。這裡，為了效率，我們肯定是選長度較短的做二分，假設為C1。
怎麼治？
也比較簡單，我們之前分析了：就是比較L1,L2和R1,R2。
- L1>R2，把C1減小，C2增大。—> C1向左二分
- L2>R1，把C1增大，C2減小。—> C1向右二分
越界問題
如果C1或C2已經到頭了怎麼辦？
這種情況出現在：如果有個數組完全小于或大于中值。可能有4種情況：
C1 == 0 —— 數組1整體都比中值大
C1 == 2 x n —— 數組1整體比中值小
C2 == 0 —— 數組1整體都比中值小
C2 == 2 x m —— 數組1整體比中值大
具體實作
nums1
大小為n，
nums2
大小為m。預設在長度小的數組上進行二分查找。如果n>m，交換。
根據“虛拟數組”，兩個虛拟數組包含
#
一共
有2m+2n+2
個元素。若
nums1
割
c1
，則表示
nums1
左邊有
c1
個數字，而總共數字有
m+n
個，為了兩個數組在割的左右邊總數相等，是以
c2= m+n-c1
low
和
high
是二分查找的區間頭和尾。
low
初始值為0（
[# 1 # 4 # 7 # 9 #]最左邊的#
），
high
初始值為
2*n
（
[# 1 # 4 # 7 # 9 #]最右邊的#
），割
c1=(low+high)/2
，表示
c1
從
nums1
數組正中間位置開始，
c2=m+n-c1
，nums1左邊和nums2左邊元素數量 = nums1右邊和nums2右邊元素數量。
當越界時，巧妙設定
INT_MIN
和
INT_MAX
，使其中一個割無效。
如
nums1 = [1 2]
nums2 = [3 4 5 6 7 8]
，因為nums1整體小于nums2，則經過幾次循環後，c1 = 4，l1 = 2，r1 = INT_MAX。c2 = 4，l2 = 4，r2 = 5。low = high =4，此時因為滿足了左邊整體<=右邊，是以會break跳出循環，然後
return (max(l1,l2) + min(r1,r2))/2.0
，此時其實傳回的就是nums2中割左右兩端的中位數。
代碼
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
if(n > m)
return findMedianSortedArrays(nums2,nums1);
int c1,c2,l1,l2,r1,r2,low =,high = *n;
while(low <= high){
c1 = (low + high)/;
c2 = m + n - c1;
l1 = (c1==)?INT_MIN:nums1[(c1-)/];
r1 = (c1==*n)?INT_MAX:nums1[c1/];
l2 = (c2==)?INT_MIN:nums2[(c2-)/];
r2 = (c2==*m)?INT_MAX:nums2[c2/];
if(l1 > r2){
high = c1 - ;
}
else if (l2 > r1){
low = c1 + ;
}
else break ;
}
return (max(l1,l2) + min(r1,r2))/;
}
};
LeetCode具體實作代碼和詳細解題報告：https://github.com/zhengjingwei/LeetCode