【LeetCode系列】Day8 有序数组的中位数 Median of Two Sorted Arrays

问题描述： 

解决方案： 

因为题目中给出的是已排序的数组，因此将问题转化为求第 k 小的数，当两个数组大小之和为奇数时，找第 小的数；当两数组之和为偶数时，找中间两个数之和除以2即可，中间两个数分别为第和小的数。

假设找第k小的数需要在数组A中找p次，在数组B中找q次，则 p + q = k。k已知而p和q未知，因此目的就是通过二分k找到p。

A[start1 + p - 1]代表的含义是指数组A“前进”了p步，对应于数组B需要“前进”q步。

①若A[start1 + p - 1] = B[start2 + q - 1]，意味着已经找到，第k个数 kth = A[start1 + p - 1] = B[start2 + q -1]。因为A和B都是有序的，因此从A[start1]到A[start1 + p - 1]（共p - 1 + 1个数）、B[start2]到B[start2 + q - 1]（共q - 1 + 1个数）也是有序的，如果将这两个子数组合并成一个数组则总共有 p - 1 + q - 1 + 2= k个数，而其中最大的数就是A[start1 + p - 1] = B[start2 + q - 1]，即第k小的数（注意每个数组都是从小到大排序的，并不需要关心合并后的内部顺序）。

②若A[start1 + p - 1] < B[start2 + q - 1]，意味着数组A中A[start1 + p - 1]之前的数字全都小于B[start2 + q - 1]（因为数组A是从小到大排序的），因此第k小的数一定不会在数组A的前p个数中，因此我们可以把它舍弃以后进行递归操作，但递归时因为我们舍弃了前面的p个数，因此下一步就是找第 k - p小的数了。

③若A[start1 + p - 1] > B[start2 + q - 1]，与上面情况类似，舍弃数组B的前q个元素，递归找第 k - q 小的数。

 

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int total = m + n;
        if((total % 2) == 1){
            return findKthNumber(A, m, 0, B, n, 0, total / 2 + 1);    //找到第total/2+1小的数
        }else{
            return (findKthNumber(A, m, 0, B, n, 0, total / 2) + findKthNumber(A, m, 0, B, n, 0, total / 2 + 1)) / 2;
        }
    }
    
    public double findKthNumber(int[] A, int m, int start1, int[] B, int n, int start2, int k){
        //一定注意这三个if的顺序
        if(m > n){    //保证A的长度一定小于B
            return findKthNumber(B, n, start2, A, m, start1, k);
        }
        if(m == 0){    //如果一个数组长度为0，则只要直接返回另一个数组的第k个元素即可
            return B[start2 + k - 1];
        }
        if(k == 1){    //返回第1小的数只要比较当前A和B中最小的即可
            return Math.min(A[start1], B[start2]);
        }
        //第k小的数在数组A中找了p次，在数组B中找了q次，p + q = k
        //二分：实际上是二分k找p
        int p = Math.min(k/2, m);    //若p > m会越界， 因此返回两者中的小值
        int q = k -p;
        if(A[start1 + p - 1] == B[start2 + q - 1]){    //说明已找到
            return A[start1 + p - 1];
        }else if(A[start1 + p - 1] < B[start2 + q - 1]){
            return findKthNumber(A, m - p, start1 + p, B, n, start2, k - p);
        }else{
            return findKthNumber(A, m, start1, B, n - q, start2 + q, k - q);
        }
    }
}

参考：

https://www.jianshu.com/p/9bd57fd52062

https://blog.csdn.net/yutianzuijin/article/details/11499917

https://leetcode.com/problems/median-of-two-sorted-arrays/solution/