4. Median of Two Sorted Arrays

<p><p>There are two sorted arrays <b>nums1</b> and <b>nums2</b> of size m and n respectively.</p>

<p>Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).</p>

<p><b>Example 1:</b><br />
<pre>
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
</pre>
</p>

<p><b>Example 2:</b><br />
<pre>
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
</pre>
</p></p>

解题思路

这道题的意思是求出两个已排序好的数列的中位数，也就是找到第<b>(m + n) / 2</b>的哪个数。（奇偶暂不讨论）

现在的问题转化为如何在数列中找到第k大的数。

寻找第k大的数

如果只有一个数列，答案是显而易见的~

现在有两个数列，我们能不能把两个数列简化为一个数列呢？答案是可以的，那就是分治。

怎么分治？

分治的思想十分简单，就是把一个大问题不断地分解为若干个小问题，直到小问题能在线性时间内解决。治，在我们这里，就是两个数列变为了一个数列。

那么怎么“分”呢？

我们分别取两个数列的中位数，分别为a[mid]和b[mid] (不妨设a[mid] > b[mid]),他们前面分别有num1和num2个数。如果k大于num1+num2,那么说明我们要找的数不在最小的那部分，接下来我们要去a数列全段和b数列后半段去寻找；如果k小于num1+num2,那么说明我们要找的数不在最大的那部分，接下来我们要去a数列前段和b数列全段去寻找。这样做的时间复杂度为O（nlogn），只不过底数不是2，而是4/3。

好了，现在我们可以在两个数列中寻找第k大的数了。接下来只要对奇偶分类，我们就可以很容易地求出两个数来中的中位数了~

代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        double res;
        if ((m+n) % 2 == 0) {
            res = ((double)(findKth(nums1, 0, m-1, nums2, 0, n-1, (m + n) / 2)) + (double)(findKth(nums1, 0, m-1, nums2, 0, n-1, (m + n) / 2 +1))) / 2;
        } else {
            res = (double)(findKth(nums1, 0, m-1, nums2, 0, n-1, (m + n) / 2 + 1));
        }
        return res;
    }
private:
    int findKth(vector<int>& nums1, int aL, int aR, vector<int>& nums2, int bL, int bR, int k) {
        //printf("aL=%d aR=%d bL=%d bR=%d k=%d\n", aL, aR, bL, bR, k);

        if (aL > aR) return nums2[bL + k - 1];
        if (bL > bR) return nums1[aL + k - 1];
        
        int aMid = (aR - aL) / 2 + aL;
        int bMid = (bR - bL) / 2 + bL;

        if (nums1[aMid] <= nums2[bMid]) {
            if (k <= (aMid - aL) + (bMid - bL) + 1) {
                return findKth(nums1, aL, aR, nums2, bL, bMid - 1, k);
            } else {
                return findKth(nums1, aMid + 1, aR, nums2, bL, bR, k - (aMid - aL + 1));
            }
        } else {
            if (k <= (aMid - aL) + (bMid - bL) + 1) {
                return findKth(nums1, aL, aMid - 1, nums2, bL, bR, k);
            } else {
                return findKth(nums1, aL, aR, nums2, bMid + 1, bR, k - (bMid - bL + 1));
            }
        }
        return 0;
    }
};