有序数组的中位数

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

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0

中位数定义法

求中位数，即求位置在中间的数。这是一种很好理解并实现的方法。根据定义，我们可以使用指针指向最小的数字开始，之后指向到比这个数字大的最小的数字。经过两组数组的长度的一半。即我们要找的中位数。时间复杂度为O((m+n)/2)。空间复杂度为O(1)。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    
    int halfLength = (nums1.length + nums2.length) / 2;
    int i = 0,j = 0,cur = 0;

    int[] start = new int[halfLength + 1];
    while(cur <= halfLength){
        if(i == nums1.length && j == nums2.length){
            break;
        } else if(i == nums1.length){
            start[cur] = nums2[j++];
        } else if(j == nums2.length){
            start[cur] = nums1[i++];
        } else if (nums1[i] < nums2[j]){
            start[cur] = nums1[i++];
        } else{
            start[cur] = nums2[j++];
        } 
        cur++;
    }
    
    if((nums1.length + nums2.length) % 2 == 1){
        return (double)start[cur - 1];
    } else {
        return (start[cur - 2] + start[cur - 1])/2.0;
    }
}

统计方法

按照中位数的定义，如果将一组有序数字分为两半，若这组数字的数字个数为偶数，则中位数为前一半最大的数和后一半最小的数字和的一半。若为数字个数为奇数，则中位数为前一半最大的数。

对于两组数字。我们可以将其合并为一组数字，然后根据上述的方式进行寻找。

如数字

1 2 3 4 5 
    3 4 5  

我们很容易会发现，这个中位数就是 （3+4）/2 = 3.5。

我们中间可以画一条拆分线，拆分线的左边就是两半中小的数字，右边就是两年中大的数字。

1 2 3 | 4 5 
    3 | 4 5  

对于奇数，同理也如此。

1 2 3 | 4
    3 | 4 5

因此我们的任务就是找到 这一条拆分线。

设置两个指针i 和 j。j 随着 i 动而动。i和j的关系就是 j = (m+n+1)/2 - i，其中m，n为两个数组的长度。我们可以将其短的数组放在前面，将长的数组放在后面整合成新的数组。这么做可以避免j出现溢出的情况。

调整i，指导找出符合条件的拆分线的条件的i。

我们要找的拆分线处满足的条件就是 A[i] ≥ B[j - 1]，A[i - 1] ≤ B[j]。

3 4 5 1 2 3 4 5

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;
    if (m > n) { // to ensure m<=n
        int[] temp = A; A = B; B = temp;
        int tmp = m; m = n; n = tmp;
    }
    int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
    while (iMin <= iMax) {
        int i = (iMin + iMax) / 2;
        int j = halfLen - i;
        if (i < iMax && B[j-1] > A[i]){
            iMin = i + 1; // i is too small
        }
        else if (i > iMin && A[i-1] > B[j]) {
            iMax = i - 1; // i is too big
        }
        else { // i is perfect
            int maxLeft = 0;
            if (i == 0) { maxLeft = B[j-1]; }
            else if (j == 0) { maxLeft = A[i-1]; }
            else { maxLeft = Math.max(A[i-1], B[j-1]); }
            if ( (m + n) % 2 == 1 ) { return maxLeft; }

            int minRight = 0;
            if (i == m) { minRight = B[j]; }
            else if (j == n) { minRight = A[i]; }
            else { minRight = Math.min(B[j], A[i]); }

            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0;
}

二分（转换成寻找第k小的问题）

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int total = nums1.length + nums2.length;
    return (getKmin(nums1,0,nums2,0,(total+ 1)/2) + getKmin(nums1,0,nums2,0,(total + 2)/2))/2.0;
}
public double getKmin(int[] nums1,int m, int[] nums2,int n,int k){
    if(m > nums1.length - 1){
        return nums2[n + k -1];
    }
    if(n > nums2.length -1){
        return nums1[m + k - 1];  
    }
    if(k == 1){
        return Math.min(nums1[m],nums2[n]);
    }
    
    int min1 = Integer.MAX_VALUE;
    int min2 = Integer.MAX_VALUE;
    if(m + k/2 -1 < nums1.length){
        min1 = nums1[m + k/2 -1];
    }
    if(n + k/2 -1 < nums2.length){
        min2 = nums2[n + k/2 -1];
    }
    
    return min1 < min2 ? getKmin(nums1,m + k/2,nums2,n,k-k/2):getKmin(nums1,m,nums2,n+k/2,k-k/2);
}