輸入：int nums1[1,3,5,8] int nums2[2,9,10,11]

過程：求兩個(gè)排序的數(shù)組的中位數(shù)

輸出：6.5

注意：數(shù)組排序方式一致，都是升序或者都是降序

算法：

• 求中位數(shù)說白了就是求特殊的第k大或者第k、k+1大的數(shù)。但是這里比較棘手的是要在兩個(gè)數(shù)組中求
• 題目時(shí)間復(fù)雜度有要求log(m+n)，基本確定使用二分查找，難點(diǎn)就在于怎么在兩個(gè)數(shù)組中實(shí)現(xiàn)二分查找。

思路：

基本知道求兩數(shù)組中位數(shù)有以下兩種情況：

• 當(dāng)m+n為偶數(shù)，中位數(shù)=(數(shù)組[(m+n)/2]+數(shù)組[(m+n)/2+1])/2.0
• 當(dāng)m+n奇數(shù)時(shí)，中位數(shù)=數(shù)組[(m+n)/2]

由上可知，假設(shè)m+n=k，要求的就是兩個(gè)數(shù)組的第k/2大值或者第k/2+1大值，所以需要設(shè)置一個(gè)函數(shù)來求第k大值。如果數(shù)組1為空，第k大值就在數(shù)組2中，反過也是一樣。如果k=1說明求的是最小值，只需返回判斷數(shù)組1[0]和數(shù)組2[0]中的較小值即可。

過一遍算法：假設(shè)數(shù)組1 arr1 = [1,3,5,8] 數(shù)組 arr2 = [2,9,10,11]，這里我們知道k=4 or 5(因?yàn)楹喜⒑蟮拈L度為偶數(shù))
先求第4大，

比較arr1[m/2]和arr2[n/2]，明顯arr1[m/2]小于arr2[n/2]，所以我們知道arr[0]_{arr[m/2]都小于arr2[n/2]；所以下一步就需要把目標(biāo)定在arr1[m/2+1]}arr[m-1]；
我們查找的范圍縮小到arr1[m/2+1]_{arr[m/2+m/2]和arr2[0]}arr[n/2]；知道查找的范圍縮小為1，就找到我們要找的第4大的值為5，
同理可求出第5大的值為8，平均值就是要求的中位數(shù)6.5

查找第k大函數(shù)如下：

int findKth(vector<int>& nums1, int m, vector<int>& nums2, int n, int k)
    {
        if (m >= nums1.size()) return nums2[n + k - 1];
        if (n >= nums2.size()) return nums1[m + k - 1];
        if (k == 1) return min(nums1[m], nums2[n]);

        int p1 = m + k / 2 - 1;
        int p2 = n + k / 2 - 1;
        int mid1 = p1 < nums1.size() ? nums1[p1] : INT_MAX;
        int mid2 = p2 < nums2.size() ? nums2[p2] : INT_MAX;
        if (mid1 < mid2)
        {
            return findKth(nums1, m + k / 2, nums2, n, k - k/2);
        }
        else
        {
            return findKth(nums1, m, nums2, n + k/2, k- k/2);
        }
    }

求中位數(shù)代碼如下：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
       int len = nums1.size() + nums2.size();
       if (len % 2 == 0) {
           return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
       }
       return findKth(nums1, 0, nums2, 0, (len + 1) / 2);
   }