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)).

Example1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example2

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

分析

解法一:

思路来自Very concise O(log(min(M,N))) iterative solution with detailed explanation 看到O(log (m+n))一般来说就是分治法或是二分搜索,一个数组(长度为N)在中间切一刀,那它左边的索引L为(N-1)/2,右边的索引R为N/2.如N=3,L=1,R=1.N=4,L=1,R=2.那这个数组的中值(L+R)/2=(A[(N-12)+A[N/2]])/2. 要处理两个数组的情况,虚拟加入一些占位符,比如’#‘,虚拟加并未真实加入.如

[6 9 13 18] -> [# 6 # 9 # 13 # 18 #]  (N =4)
				0 1 2 3 4  5 6  7 8	  (N'=9)
				
[6 9 11 13 18] -> [# 6 # 9 # 11 # 13 # 18 #]	(N=5)
				0 1 2 3 4  5 6  7  8 9 10 11	(N'=11)

加入一些占位符后,长度为2*N+1.并且中位数为index为Nth的数(从0开始算).由于index(L)=(N-1)/2,index®=N/2.可以推理出这一刀切的任意位置cutPosition,index(L)=(cutPosition-1)/2,index®=(cutPosition-1)/2. 看到这就知道为啥要虚拟加入’#’

例子:

A1: [# 1 # 2 # 3 # 4 # 5 #] (N1=5,N'=11)
A2: [# 1 # 1 # 1 # 1 #] (N2=4,N'=9)

两个数组一共有2N1+2N2+2个位置,有两刀占了两个位置.求两个原数组的中位数,就相当求(N1+N2)th.如果C2=2,那么C1=4+5-2=7.

L1=A1[(C1-1)/2]=A1[(7-1)/2]=A1[3]=4;R1=A1[C1/2]=A1[7/2]=A1[3]=4;
L2=A2[(C2-1)/2]=A2[(2-1)/2]=A2[0]=1;R2=A2[C2/2]=A2[2/2]=A2[1]=1;

要想保证这两刀切的对,必须保证L1<=R1&&L1<=R2&&L2<=R1&&L2<=R2

越界问题.0th(first)或是2Nth(last)这里用INT_MIN,INT_MAX控制.

解法二,相对好理解一些

Solution1

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 
        int m = nums1.size();
        int n = nums2.size();
        //保证m小于n
        if (m > n)
            return findMedianSortedArrays(nums2,nums1);
        int mid1,mid2,L1,L2,R1,R2,low=0,high=2*m;
        while(low <= high)
        {
            //取较短的数组二分切
            mid1 = (low+high)/2;
            //
            mid2 = m+n-mid1;
            L1 = mid1==0?INT_MIN:nums1[(mid1-1)/2];
            L2 = mid2==0?INT_MIN:nums2[(mid2-1)/2];
            R1 = mid1==2*m?INT_MAX:nums1[mid1/2];
            R2 = mid2==2*n?INT_MAX:nums2[mid2/2];
            
            if (L1 > R2)
                //数组1切的太靠右,需要向左切
                high=mid1-1;
            else if (L2 > R1)
                //数组1切的太靠左,需要向右切
                low=mid1+1;
            else
                return (max(L1,L2)+min(R1,R2))/2.0;
        }
        return -1;
    }
};

Solution2

class Solution
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int k = (m + n) / 2;
        //分奇偶判断
        if((m+n)%2==0){
            return (findKth(nums1,nums2,0,0,m,n,k)+findKth(nums1,nums2,0,0,m,n,k+1))/2;
        }   else {
            return findKth(nums1,nums2,0,0,m,n,k+1);
        }
        
    }
private:
    double findKth(vector<int>& arr1, vector<int>& arr2, int start1, int start2, int len1, int len2, int k){
        //保证数组1的长度比数组2短
        if (len1 >len2) {
            return findKth(arr2, arr1, start2, start1, len2, len1, k);
        }
        if (len1==0) {
            return arr2[start2+k-1];
        }
        if (k==1) {
            return min(arr1[start1], arr2[start2]);
        }
        //防止后面越界
        int p1 = min(k/2, len1);
        int p2 = k - p1;
        if (arr1[start1+p1-1]<arr2[start2+p2-1])
        {
            //说明arr1的前p1个元素不在搜索范围内,丢弃
            return findKth(arr1, arr2, start1+p1, start2, len1-p1, len2, k-p1);
        }
        else if(arr1[start1+p1-1]>arr2[start2+p2-1])
        {
            //说明arr2前p2的元素不在搜索范围内,丢弃
            return findKth(arr1, arr2, start1, start2+p2, len1, len2-p2, k-p2);
        }
        else
        {
            //相等说明找到第k个元素
            return arr1[start1+p1-1];
        }
    }
};
 
comments powered by Disqus