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个元素。

针对本题，找两个已知排序数组的中位数，如果两个数组长度和为len,若

• len为偶数，则寻找第len/2与len/2+1元素之和的一半
• len为奇数，则寻找第len/2+2的元素

解题方法

给出寻找第K大元素的通用解法

常规做法1

由于两个数组已经排序，直接merge两个数组，然后取出所需元素即可。

常规解法2

由于数组已排序，且只需获得第K个元素，故使用两个整数i和j分别指向数组A和B的起始位置，整数m记录当前遍历的元素个数，if(A[i]<B[j]) i++；m++,否则j++;m++;当m==k时，取出元素即为所求

类二分查找求解方法

考虑到数组有序，采用类似二分查找的方法，每次从数组中删除K/2个元素。

假设A和B的元素个数都大于k/2，则将A中第k/2个元素（即A[K/2-1])和B中第K/2个元素(即B[k/2-1])进行比较，可考虑如下三种情况（假设K为偶数)：

• A[K/2-1]<B[K/2-1] 此时A[0]至A[K/2-1]均在A U B 的K个元素范围内，故可删去
• A[K/2-1]>B[K/2-1] 此时B[0]至B[K/2-1]均在A U B 的K个元素范围内，故可删去
• A[K/2-1]>B[K/2-1] 此时找到第K个元素，直接返回A[K/2-1]

上述过程针对k为奇数和偶数均成立，可自行推导

所以如果要查找第K个元素，可以写一个递归函数，递归函数停止的条件为

• 当A或B为空时，直接返回B[K-1]或A[K-1]
• 当K==1时，返回min(A[0],B[0])
• 当A[K/2-1]>B[K/2-1]时，返回A[K/2-1]或B[k/2-1]

解题代码

class Solution {
private:
    double findKelement(vector<int>& nums1, vector<int>& nums2,int i1,int i2,int j1,int j2,int k ){
        if(i1>=i2) return nums2[j1+k-1];    //若此时nums1已全部删除，则直接从nums2中取出所需元素即可
        else if(j1>=j2) return nums1[i1+k-1];   //若此时nums2已全部删除，则直接从nums1中取出所需元素即可
        else if(k==1) return min(nums1[i1],nums2[j1]);      //当k==1时，停止递归，直接取出当前最小元素即可
        
        int m1=min(i2-1,i1+k/2-1),m2=min(j2-1,j1+k/2-1);        //考虑到数组剩余元素的个数可能已不足k/2
        if(nums1[m1]<nums2[m2]) return findKelement(nums1,nums2,m1+1,i2,j1,j2,k-m1+i1-1);
        else return findKelement(nums1,nums2,i1,i2,m2+1,j2,k-m2+j1-1);
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1=nums1.size(),len2=nums2.size();
        if((len1+len2)%2==0) return (findKelement(nums1,nums2,0,len1,0,len2,(len1+len2)/2)+findKelement(nums1,nums2,0,len1,0,len2,(len1+len2)/2+1)+0.0)/2;
        else return findKelement(nums1,nums2,0,len1,0,len2,(len1+len2)/2+1);
    }
};