4. Median of Two Sorted Arrays

问题描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

问题分析

这道题之前做了没有记录下来，导致现在又忘了。。。
现在觉得，此题关键在于将寻找中位数这个问题转换为寻找第K大的数。

update 5.3
今天看到一个新的思路。
找median其实就是将nums1, nums2各分割为左右两部分，使得两个序列的左部分合并后与右部分合并后长度相等，且左部分的最大值不大于右部分的最小值。
设nums1长度比nums2小，那么我们用二分的方法查找nums1的分割点，对于每个分割点，我们可以找到nums2中与之相对应的分割点（因为两个左部分个数之和是所有元素个数的一半）。
实现起来的难度主要在于边界条件。

AC代码1

class Solution {
public:
    double findK(vector<int>& nums1, vector<int>& nums2, int p1, int p2, int len1, int len2, int k){
        if (p1 == len1)
            return nums2[p2+k-1];
        if (p2 == len2)
            return nums1[p1+k-1];
        if (k == 1){
            return min(nums1[p1], nums2[p2]);
        }
        bool flag1 = (len1-p1) >= k/2;
        bool flag2 = (len2-p2) >= k/2;
        if (flag1 && flag2){
            if (nums1[p1+k/2-1] > nums2[p2+k/2-1])
                return findK(nums1, nums2, p1, p2+k/2, len1, len2, k-k/2);
            else if (nums1[p1+k/2-1] < nums2[p2+k/2-1])
                return findK(nums1, nums2, p1+k/2, p2, len1, len2, k-k/2);
            else if (k % 2 == 0)
                return nums2[p2+k/2-1];
            else
                return findK(nums1, nums2, p1+k/2, p2+k/2, len1, len2, 1);
        }
        else if (flag1){
            return findK(nums1, nums2, p1+k/2, p2, len1, len2, k-k/2);
        }
        else
            return findK(nums1, nums2, p1, p2+k/2, len1, len2, k-k/2);
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        int k = (len1 + len2) / 2;
        if ((len1 + len2) % 2 == 0){
            double a = findK(nums1, nums2, 0, 0, len1, len2, k);
            double b = findK(nums1, nums2, 0, 0, len1, len2, k+1);
            return (a + b)/2;
        }
        else
            return findK(nums1, nums2, 0, 0, len1, len2, k+1);
    }
};

Runtime: 29 ms, which beats 99.11% of cpp submissions.

AC代码2

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);
        if (n == 0){
            if (m % 2 == 0)
                return (nums2[m/2] + nums2[m/2 - 1])/2.0;
            else
                return nums2[m/2];
        }
        int mini = 0;
        int maxi = n;
        int i, j;
        while (mini <= maxi){
            i = (mini + maxi)/2;
            j = (m + n)/2 - i;
            // cout << i << ' ' << j << endl;
            if ((i >= n  || j-1 < 0 || nums1[i] >= nums2[j-1]) && (i-1 < 0 || j >= m || nums1[i-1] <= nums2[j])){
                break;
            }
            else if (i >= m || j < 0 || nums1[i-1] > nums2[j])
                maxi = i-1;
            else
                mini = i+1;
            // cout << "min-max:" << mini << ' ' << maxi << endl;
        }
        // cout << i << ' ' << j << endl;
        double rst = 0;
        if ((m+n) % 2 == 0){
            if (i >= n){
                if (j <= 0)
                    return (nums1[n-1] + nums2[0])/2.0;
                else{
                    if(nums1[n-1] > nums2[j-1])
                        return (nums2[j] + nums1[n-1])/2.0;
                    else
                        return (nums2[j] + nums2[j-1])/2.0;
                }
            }
            else if(i <= 0){
                if (j >= m)
                    return (nums1[0] + nums2[m-1])/2.0;
                else {
                    if(nums1[0] < nums2[j])
                        return (nums2[j-1] + nums1[0])/2.0;
                    else
                        return (nums2[j] + nums2[j-1])/2.0;
                }
            }
            else{
                if (nums1[i-1] > nums2[j-1])
                    rst += nums1[i-1];
                else
                    rst += nums2[j-1];
                if (nums1[i] < nums2[j])
                    rst += nums1[i];
                else
                    rst += nums2[j];
                return rst/2.0;
            }
        }
        else{
            if (i >= n){
                if (j <= 0)
                    return nums2[0];
                else
                    return nums2[j];
            }
            else if(i <= 0)
                if (j >= m)
                    return nums2[m-1];
                else
                    return nums2[j] < nums1[0] ? nums2[j] : nums1[0];
            else{
                if (nums1[i] > nums2[j])
                    return nums2[j];
                else
                    return nums1[i];
            }
        }
    }
};

讲真，写得相当丑了……
Runtime: 32 ms, which beats 95.90 % of cpp submissions.