HelloKenLee

Leetcode 4 Median of Two Sorted Arrays 解题报告

Posted on By KenLee

题目信息

题目: 4. Median of Two Sorted Arrays
难度: Hard
正确率: 21.2%
问题描述:

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

问题分析

  该问题的大意是,给出两个升序数组nums1(长度为N)和nums2(长度为M),要你找出这两个数组合在一起的大数组(长度为N+M)的中位数。

解题思路

  这个问题描述很简单,最容易想到的思路是按照归并排序的merge过程把两个数组合并,然后取中位数即可。时间复杂度为O(M+N),空间复杂度为O(1)。 尽管不知道为什么这样做也能通过,不过明显是不符合题目要求的,因为题目要求时间复杂的至多为O(log(M+N))。
  看到是查找问题,要求的时间复杂度为对数级别,很容易想到的思路是二分查找了。问题是如何在两个有序的数组中不合并而直接进行二分查找。我想到的一种方法是,分别对两个数组进行二分试探,计算num[mid]。然后比较那个值小,就认为较小的那次试探是有效的试探。举个例子,比如:

//k=6
nums1 = [1,3,5,7,9,11]; //n = 6
nums2 = [2,4,6,8,10]; //m = 5

  假设我们要在两个数组中找第k个数。我们因为N+M=11, 所以我们要找第k=6个数。我们第一次计算nums1[mid]=nums1[3]=7nums2[mid]=nums[2]=6。这时候6<7,所以相当于我们能跳过nums[2]之前的数。现在相当于变成

//k=6-2=4
nums1 = [1,3,5,7,9,11]; //n = 6
nums2 = [6,8,10]; //m = 3

  现在我们相当在里面找第3个数,再一次计算nums1[mid]=nums[3]=7nums2[mid]=nums2[1]=8。因此我们又可以跳过nums2[1]前面的数。如此类推,最后变成:

//k=1
nums1 = [7,9,11]; //n = 3
nums2 = [8,10]; //m = 2

  这时候,我们要找的就是地一个数了,那么返回nums1[0]nums2[0]之中小的数即可。
  然而,O(log(M+N))就是最优的算法了吗? 我在逛discuss的时候发现其实发现算法可以优化到O(log(min(N,M)))。怎么做呢?事实上思路也是二分查找,不过只在一个数组上做二分,然后计算出另一个数组的二分。具体可以看代码。
  

结果分析

  • 时间复杂度: 第一种算法O(log(M+N)); 第二种算法O(log(min(M,N)))。
  • 空间复杂度: O(1),没有用到额外空间。
  • 通过时间: 35 ms
  • 击败: 95.43%的提交

源代码

//Time O(lg(N+M))方法
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int len1=nums1.size(),len2=nums2.size();
        if(len1+len2==0)
            return 0;
        int m1=(len1+len2+1)/2,m2=(len1+len2+2)/2;
        double r1=findKthRec(len1>0?&nums1[0]:nullptr,len1,len2>0?&nums2[0]:nullptr,len2,m1);
        double r2=findKthRec(len1>0?&nums1[0]:nullptr,len1,len2>0?&nums2[0]:nullptr,len2,m2);
        return (r1+r2)/2.0;
    }
private:
    double findKthRec(int *num1,int len1,int *num2,int len2,int k){
        //保证num1比num2长
        if(len1<len2){
            return findKthRec(num2,len2,num1,len1,k);
        }
        //如果num2长度为0
        if(len2==0){
            return num1[k-1];
        }
        //如果要找的是第一个
        if(k==1){
            return min(num1[0],num2[0]);
        }
        int mid1=min(len1,k/2),mid2=min(len2,k/2);
        if(num1[mid1-1]>num2[mid2-1]){
            return findKthRec(num1,len1,num2+mid2,len2-mid2,k-mid2);
        }else{
            return findKthRec(num1+mid1,len1-mid1,num2,len2,k-mid1);
        }
        return 0;
    }
};
//Time O(lgmin(N,M))方法
class Solution {
public:
     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int N1 = nums1.size();
        int N2 = nums2.size();
        if (N1 + N2==0)
            return 0;
        if (N1 < N2) return findMedianSortedArrays(nums2, nums1);	// Make sure A2 is the shorter one.
        
        if (N2 == 0) return ((double)nums1[(N1-1)/2] + (double)nums1[N1/2])/2;  // If A2 is empty
        
        int lo = 0, hi = N2 * 2;
        while (lo <= hi) {
            int mid2 = (lo + hi) / 2;   // Try Cut 2 
            int mid1 = N1 + N2 - mid2;  // Calculate Cut 1 accordingly
            
            double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2];	// Get L1, R1, L2, R2 respectively
            double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
            double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
            double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];
            
            if (L1 > R2) lo = mid2 + 1;		// A1's lower half is too big; need to move C1 left (C2 right)
            else if (L2 > R1) hi = mid2 - 1;	// A2's lower half too big; need to move C2 left.
            else return (max(L1,L2) + min(R1, R2)) / 2;	// Otherwise, that's the right cut.
        }
        return -1;
    } 
};