最簡單的方法是兩個數(shù)組一個一個往前找找到中間那個數(shù)結(jié)束。但是時間復雜度是O(m+n)抓艳。既然要求復雜度為O(log(m+n))，所以幾乎一定是二分查找玷或。而且應該也不用一個挨著一個找。
許多corner case干擾推導：
- m + n是奇數(shù)還是偶數(shù)偏友？奇數(shù)的話要取第(m+n)/2 + 1個數(shù)。偶數(shù)的話要取第(m+n)/2個和第(m+n)/2 + 1個數(shù)的平均數(shù)位他？解決方法是設置helper函數(shù)，題目本質(zhì)為：取兩個數(shù)組的第k大的數(shù)鹅髓。所以判斷先判斷奇偶，偶的話返回兩個helper結(jié)果的平均數(shù)窿冯。
- m和n誰大？應該一直假設m比n大醒串，如果不是的話执桌，helper兩個數(shù)組反過來厦凤。
- 開始二分法，兩邊都取第k/2個數(shù)（實際編碼時候index=[k/2] -1）
a. 如果m(k/2) < n(k/2)较鼓， 那m這邊0~k/2都在前k個里面，換言之博烂，中位數(shù)（第k個大的數(shù)）肯定不在這里面。（為什么禽篱？反證法，如果中文數(shù)在m的前k/2里面躺率，那m這邊最多k/2 - 1個數(shù)，n那邊第k/2個比m這邊第k/2個大悼吱，所以肯定也不是中位數(shù)，所以也是最多k/2 - 1個數(shù)后添，最后加一塊兒k-2個數(shù)，少于k個數(shù)遇西。
所以要把m這邊的前k/2個都算進去，然后繼續(xù)找m后一半和n的全部粱檀，找第k - k/2 = k/2個數(shù)
b. 如果m(k/2) = n(k/2)，那如果k為奇數(shù)茄蚯，就是這個數(shù)后面那個m和n里面比較小的數(shù)。如果k為偶數(shù)第队，就是這倆數(shù)。 - 特殊情況
a. 最后越來越少不夠k/2： 所以要取pa = min(k/2, m),另一邊 pb = k - pa而不是簡單的兩邊都是k/2
b. k = 1時上面算法不需要凳谦，也是停止點， 否則pa = 0, pb = 1, 數(shù)組index = pa -1是非法值。
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.Length;
int n = nums2.Length;
if((m + n) % 2 == 1){
return (double)FindKthLargest(nums1, m, nums2, n, (m + n) / 2 + 1);
}
return (FindKthLargest(nums1, m, nums2, n, (m + n) / 2) + FindKthLargest(nums1, m, nums2, n, (m + n) / 2 + 1)) / 2;
}
public double FindKthLargest(int[] a, int m, int[] b, int n, int k){
if(m > n){
return FindKthLargest(b, n, a, m, k);
}
if(m == 0){
return b[k - 1];
}
if(k == 1){
return Math.Min(a[0], b[0]);
}
//Divide k into two parts
int pa = Math.Min(m, k / 2);
int pb = k - pa;
if(a[pa - 1] < b[pb - 1]){
int[] subArray = new int[m - pa];
Array.Copy(a, pa, subArray, 0, m- pa);
return FindKthLargest(subArray, m - pa, b, n, k - pa);
}
else if (a[pa - 1] > b[pb - 1]){
int[] subArray = new int[n - pb];
Array.Copy(b, pb, subArray, 0, n - pb);
return FindKthLargest(a, m , subArray, n - pb, k - pb);
}
return a[pa - 1];
}
}
