4.【困难】寻找两个有序数组的中位数

题目描述

1.merge过程（时间复杂度不达标）

2.寻找第k小的数

思路

求中位数，其实就是求第 $k$k 小的数的一种特殊情况
在两个排序数组中怎么找第 $k$k 小的数呢？
答：我们可以在两个数组中都找第 $k/2$k/2 小的数

由于 $4>3$4>3 ，因此 $nums2$nums2 中的 $3 (含3在内)$3(含3在内) 的之前的元素不可能是第 $k$k 小的数，可以舍弃


最后 ，k=1 的时候，我们在 nums1 和 nums2 中对第一个元素进行比较，找到二者中最小的即可返回

• 时间复杂度：每进行一次循环，就减少 $k/2$k/2 个元素，因此时间复杂度是 $O(logk)$O(logk) ，而 $k=(m+n)/2$k=(m+n)/2
  因此最终的复杂度为 $O(log(m+n))$O(log(m+n))
• 空间复杂度： $O(1)$O(1)

代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //把奇数和偶数的情况合并
        int left = (m+n+1)/2;
        int right = (m+n+2)/2;
        return (findMedianSortedArrays(nums1,0,m-1,nums2,0,n-1,left) + 
        findMedianSortedArrays(nums1,0,m-1,nums2,0,n-1,right) )*0.5;
    }
    
    private double findMedianSortedArrays(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){
    //注意，此处的k代表的是第k小的元素，从1开始计数
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //确保nums1是两个数组中长度较小的
        if(len1 > len2){
            return findMedianSortedArrays(nums2,start2,end2,nums1,start1,end1,k);
        }
        //如果len1为0，那么就去nums2中找
        if(len1 == 0){
            return nums2[start2+k-1];
        }
        //如果最后k==1，可以返回二者最小的了
        if(k == 1){
            return Math.min(nums1[start1],nums2[start2]);
        }
        
        int i = start1 + Math.min(k/2,len1) - 1 ;
        int j = start2 + Math.min(k/2,len2) - 1 ;
        
        if(nums1[i] > nums2[j]){
            return findMedianSortedArrays(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
        }else{
            return findMedianSortedArrays(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
        }
    }
}

3. 数组分片

思路

代码

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { 
            return findMedianSortedArrays(B,A); // 保证 m <= n
        }
        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && B[j-1] > A[i]){ // i 需要增大
                iMin = i + 1; 
            }else if (i != 0 && j != n && A[i-1] > B[j]) { // i 需要减小
                iMax = i - 1; 
            }else { // 达到要求，并且将边界条件列出来单独考虑
                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;
    }
}