題意

找到兩個(gè)有序數(shù)組的中位數(shù)

解答一（遞歸踢械，時(shí)間復(fù)雜度O(logk)）

首先理解題意兩個(gè)關(guān)鍵點(diǎn)：有序數(shù)組和中位數(shù)

• 對于有序數(shù)組a，長度為m
  • 如果m為奇數(shù)魄藕，則中位數(shù)為第m/2+1小的數(shù)内列；
  • 如果m為偶數(shù)，則中位數(shù)為第m/2+1小與第m/2小的數(shù)的平均和泼疑；
• 對于有序數(shù)組a和b德绿，長度分別為m和n
  • 如果m+n為奇數(shù)，則兩個(gè)數(shù)組的中位數(shù)為第(m+n)/2+1小的數(shù)
  • 如果m+n為偶數(shù)退渗，則兩個(gè)數(shù)組的中位數(shù)為第(m+n)/2+1小和第(m+n)/2小的數(shù)平均和移稳；

根據(jù)上面性質(zhì)可知，只要找到第(m+n)/2+1小和第(m+n)/2小的數(shù)即可会油，該題演變成找兩個(gè)有序數(shù)組第k小的數(shù)个粱；

如何尋找兩個(gè)有序數(shù)組的第k小數(shù)？二分查找

先聲明查找第k小數(shù)的函數(shù)

/* param:
 *      a   數(shù)組a起始地址
 *      m   數(shù)組a起始地址開始的長度
 *      b   數(shù)組b起始地址
 *      n   數(shù)組b起始地址開始的長度
 */
int findKth(int* a, int m, int* b, int n, int k);

如果i=k/2翻翩，則j=k-i=k/2, 和總共k個(gè)數(shù)都许，但這k個(gè)數(shù)不一定是最小的k個(gè)數(shù)

• 
  說明的左邊部分肯定在最小的k個(gè)數(shù)里面，右邊部分可能存在數(shù)在最小的k個(gè)數(shù)里面嫂冻；
  這時(shí)候需要在和中查找第小的數(shù)

findKth(a+i, m-i, b, n, k-i);

• 
  說明的左邊部分肯定在最小的k個(gè)數(shù)里面胶征，右邊部分可能存在數(shù)在最小的k個(gè)數(shù)里面；
  這時(shí)候需要在和中查找第小的數(shù)

findKth(a, m, b+j, n-j, k-j);

• 
  說明找到第k小的數(shù)桨仿，和總共k個(gè)最小的數(shù)

二分核心流程：

int i = min(m, k/2), j = k-i;
if (a[i-1] < b[j-1]) {
    return findKth(a+i, m-i, b, n, k-i);
} else if (a[i-1] > b[j-1]) {
    return findKth(a, m, b+j, n-j, k-j);
} else {
    return a[i-1];
}

現(xiàn)在考慮邊界情況

• 且
  且
  
  所以當(dāng)k=1時(shí)不能進(jìn)入上面二分核心流程

if (k==1) return min(a[0], b[0]);`

• 由于要使用a[0]和b[0]睛低，所以a和b必須分別至少有一個(gè)元素；如果a沒有元素或者b沒有元素不能進(jìn)入k==1的判斷條件

if (m == 0) return b[k-1];
if (n == 0) return a[k-1];

• 
  
  
  如果m> n服傍，則需要將數(shù)組a和b交換

完整代碼：

class Solution {
public:
    int findKth(int* a, int m, int* b, int n, int k) {
        if (m > n) return findKth(b, n, a, m, k);
        if (m == 0) return b[k-1];
        if (k == 1) return min(a[0], b[0]);
        int i = min(m, k/2), j = k - i;
        if (a[i-1] < b[j-1]) {
            return findKth(a+i, m-i, b, n, k-i);
        } else if (a[i-1] > b[j-1]){
            return findKth(a, m, b+j, n-j, k-j);
        } else {
            return a[i-1];
        }
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if ((m+n)%2) {
            return findKth(nums1.data(), m, nums2.data(), n, (m+n)/2+1);
        } else {
            int left = findKth(nums1.data(), m, nums2.data(), n, (m+n)/2);
            int right = findKth(nums1.data(), m, nums2.data(), n, (m+n)/2+1);
            cout<<left<<" "<<right<<endl;
            return (left+right)/2.0;
        }
    }
};

解答二（非遞歸钱雷，時(shí)間復(fù)雜度O(log(min(m,n)))）

對于數(shù)組吹零，有種分隔方式罩抗，如下圖（a）所示；當(dāng)的部分長度為時(shí)灿椅，部分長度為套蒂，如下圖（b）所示钞支；

• 如果，則操刀，
• 如果伸辟，則，
• 如果且馍刮，則，

同樣的對于數(shù)組窃蹋，有種分隔方式卡啰，

• 如果，則警没，
• 如果匈辱，則，
• 如果且杀迹，則亡脸，
  

如何求數(shù)組a和b的中位數(shù)？按照上述劃分原則树酪，只要把數(shù)組a和b劃分成left和right兩部分浅碾，保證，同時(shí)续语，左邊元素都小于等于右邊元素垂谢，則中位數(shù)為。

但是數(shù)組分偶數(shù)和奇數(shù)兩種情況：

• 如果是偶數(shù)疮茄，只需要和等分即可滥朱，即，又由于整數(shù)除法是向下取值的力试，則徙邻，故也滿足，中位數(shù)為畸裳；
• 如果是奇數(shù)缰犁，將中間元素放到左邊，右邊將比左邊少一個(gè)元素躯畴，即民鼓，中位數(shù)為
  

綜合上述兩個(gè)條件蓬抄，不論m+n是奇數(shù)還是偶數(shù)丰嘉，對于數(shù)組a和b中位數(shù)來說滿足j=(m+n+1)/2-i，為了保證嚷缭，則

故中位數(shù)滿足的條件是：

• 
• 且

邊界條件：
當(dāng)m+n不論奇數(shù)偶數(shù)時(shí)

• 當(dāng)時(shí)饮亏，j=(m+n+1)/2耍贾，則最小的數(shù)都在數(shù)組b，
• 當(dāng)時(shí)路幸，i=(m+n+1)/2荐开，則則最小的數(shù)都在數(shù)組a，
• 當(dāng)且简肴，則

當(dāng)m+n為偶數(shù)時(shí)晃听，需要

• 當(dāng)時(shí)，數(shù)組a都在左邊砰识，右邊都是b能扒，
• 當(dāng)時(shí)，數(shù)組b都在左邊辫狼，右邊都是a初斑，
• 當(dāng)且，則

當(dāng)對數(shù)組a進(jìn)行二分查找位置i時(shí)膨处，相應(yīng)的數(shù)組b位置j=(m+n+1)/2-i见秤，此時(shí)數(shù)組a和數(shù)組b左右兩部分相等，中位數(shù)

完整代碼：

class Solution {
public:    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if (m > n) return findMedianSortedArrays(nums2, nums1);
        int imin = 0, imax = m, i = 0, j = 0, media = 0;
        while (imin <= imax) {
            i = (imin+imax)/2;
            j = (m+n+1)/2 - i;
            if (j-1>=0 && j-1<n && i>=0 && i<m  && nums2[j-1] > nums1[i]) {
                imin = i + 1;
            } else if (i-1>=0 && i-1<m && j>=0 && j< n  && nums1[i-1] > nums2[j]) {
                imax = i - 1;
            } else {    
                if (i == 0) media = nums2[j-1];
                else if (j == 0) media = nums1[i-1];
                else media = max(nums1[i-1], nums2[j-1]);
                break;
            }
        }
        if ((m+n)&1) return media;
        if (i == m) media += nums2[j];
        else if (j == n) media += nums1[i];
        else media += min(nums1[i], nums2[j]);
        return media*0.5;
    }
};