Leetcode #4

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);     //确保nums1长度更小
        int L1,L2,R1,R2,c1,c2,lo = 0, hi = 2*n;
        while(lo <= hi)
        {
            c1 = (lo + hi)/2;
            c2 = m + n - c1;
            L1 = (c1 == 0)?INT_MIN:nums1[(c1-1)/2];
            R1 = (c1 == 2*n)?INT_MAX:nums1[c1/2];
            L2 = (c2 == 0)?INT_MIN:nums2[(c2-1)/2];
            R2 = (c2 == 2*m)?INT_MAX:nums2[c2/2];

            if(L1 > R2)
                hi = c1 - 1;
            else if(L2 > R1)
                lo = c1 + 1;
            else
                break;
        }
        return (max(L1,L2) + min(R1,R2))/2.0;
    }
};

题目大意就是给定两个长度分别为m和n的排好序的数组，求他们合并后数组的中位数，要求复杂度小于等于O(log (m+n))。显然真的把两个数组合并的做法是要超时的，一个可行的做法如下：对于一个排好序的数组A(从0开始计数)，在其第i个数后做一个切割，则显然A[i]为切割左边最大的数，A[i+1]为切割右边最小的数。同理，对于两个排好序的数组A和B，分别在A的第i个数后和B的第j个数后做一次切割，如果A[i]<B[j+1]且B[i]<A[i+1]，说明切割左边的所有数中最大的数(即tmp=max(A[i],B[j]))也小于切割右边的数中最小的数，那么tmp就是第i+1+j+1大的数。如果切割左边的数恰为两数组总个数的一半，那么tmp就是中位数。因此，我们可以保持切割左边的数量始终为(m+n)/2，通过二分i的值来控制切割i和切割j的位置，即通过判断A[i]和B[j+1]，B[j]和A[i+1]大小来左移或右移i。

大体上的思路就是这样，剩下的问题就是奇偶。一个通用的办法是假设在数组的开头，结尾和任意两数中间添加一个符号’#’，这样每个数组的长度一定是2p+1，而i(切割)的位置减一除以2正好是A[i]。例如数组A=[#,1,#,4,#,7,#,9,#]，假设在4和7之间做切割，则i=4，(i-1)/2=1，A[i]恰为4。这样奇偶的问题也解决了，最后的代码见上。