欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-25 14:31:50
...

问题描述: 

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

解决方案: 

因为题目中给出的是已排序的数组,因此将问题转化为求第 k 小的数,当两个数组大小之和为奇数时,找第 【LeetCode系列】Day8 有序数组的中位数 Median of Two Sorted Arrays小的数;当两数组之和为偶数时,找中间两个数之和除以2即可,中间两个数分别为第【LeetCode系列】Day8 有序数组的中位数 Median of Two Sorted Arrays【LeetCode系列】Day8 有序数组的中位数 Median of Two Sorted Arrays小的数。

假设找第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/