两个有序数组的中间值(Median of Two Sorted Arrays)__By leetCode

傷城~ 2022-05-16 03:36 92阅读 0赞

*  Example

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

> `求两个有序数组的中间值`

*  One

public double findMedianSortedArrays(int[] a, int[] b) {
            int[] c = new int[a.length+b.length];
    
            for (int i = 0; i < c.length; i++) {
                c[i] = i<a.length?a[i]:b[i-a.length];
            }
    
            Arrays.sort(c);
    
            if (c.length%2 == 1){
                return c[c.length/2]*1.0;
            }else {
                return (c[c.length/2]*1.0+c[c.length/2-1])/2;
            }
        }

> 解析  
> `合并数组，然后排序，找到中间值`  
> `时间复杂度O(m+n)`  
> `空间复杂度O(m+n)`

*  Two

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;
        }

> 解析:  
> 如果m+n是偶数，那么我们相信存在Ai|Ai+1/BhalfLen-i|BhalfLen-i-1这时候，max(left)+min(right)/2就是中间值  
> 如果m+n是奇数，那么必然存在一个数，Ai\+BhalfLen-i,取Max就是中间值  
> 时间复杂度(Olog(min(m,n)))  
> 时间复杂度(O(1))