递归训练四:Leetcode 4. 寻找两个正序数组的中位数

题目描述

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

示例 4:

输入:nums1 = [], nums2 = [1]
输出:1.00000

示例 5:

输入:nums1 = [2], nums2 = []
输出:2.00000

提示:

  • nums1.length m
  • nums2.length n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

原题链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

题解

这道题有一定难度,如果两个数组的长度和为奇数的话,那么这道题简单一些;但如果两个数组的长度和为偶数时,这道题的难度顿时上升了

为什么呢?因为你要求出两个数,然后再来求平均,而且主要,这两个数可能一个数是位于 arr1 数组,而一个数是位于 arr2 数组,这会导致我们的判断逻辑变的很复杂,不信的话,你可以去试试。

当然,如果你用一个临时数组把两个数组合并起来,然后求它的中位数,这肯定简单,不过我们要的是时间复杂度为 O(log (m+n))算法,下面开始讲解。

那怎么办呢?实际上,这道题我们是可以进行一下转换,就是无论两个数组的长度和是奇数还是偶数,我们都求出第 (m+n+1)/2 小数以及第 (m+n+2)/2小数,然后求这两个数的平均数,就可以了。这样,我们就屏蔽了奇偶数的影响,会容易一点。

所以现在的问题转化为如何求两个有序数组的第 K 小数,这个也有一定难度,但比上面好多了。

下面我随便讲一下如何用递归来求:我们可以采用递归的方法不断缩小 K 的,把求第 K 小元素转化为第 (K-K/2) 小元素….我举个例子吧,比较容易理解。

我们假定 arr1 = [1, 2,3],arr2 = [3,4,5,6],K = 4。

图片

这里令 K = K- 1(说明:这里我们假设K从 0 算起,也就是有第 0 小元素,相当于令 K = K – 1)

如果不懂,你就先跟着我的思路走,之后再来想

再令

mid1 = K/2 = 1。

mid2 = K/2 = 1。

图片

假如 arr2[mid2] > arr2[mid1],那么我们要找的目标数是一定存在于 arr1[mid1+1…m] 和 arr2[0…mid2]中。而不可能存在于 arr1[0…mid1] 和 arr2[mid2+1…n] 之中。

那么问题转化为在数组 arr1[mid1+1…m]和数组 arr2[0…mid2] 寻找第(K-md1-1)小的元素,然后不断重复这个过程,直到 k < 1 或者 数组的左边界大于右边界(就是二分查找中的 left > right,那么递归就要结束了)

不过这里需要注意的是,有可能 k/2 的值是大于 m 或者 n 的,所以如果 k/2 > m 或者 n 的话,我们直接令 mid1 = m-1 或者 mid2 = n-1 就行了。

所以这道题的代码如下,下面有详细注释

class Solution {
    // 由于中位数会受长度是奇偶数的影响,所以我们可以把问题转化为求
    // 第(m+n+1)/2 小数以及第 (m+n+2)/2小数,然后求这两个数的平均数
    public double findMedianSortedArrays(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int m = arr2.length;
        // 注意是除以 2.0,因为结果有可能是小数
        return (findKth(arr1, arr2,(n+m+1)/2) + findKth(arr1,arr2,(n+m+2)/2))/2.0;
    }
        // 求第 K 小的数,这是一个辅助函数
    public int findKth(int[] arr1, int[] arr2, int k) {
        if(arr1 == null || arr1.length < 1)
            return arr2[k-1];
        if(arr2 == null || arr2.length < 1)
            return arr1[k-1];
        // 注意这个函数的参数有7个,上面那个函数的参数只有3个,同名不同函数哈
        return findKth(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k);
    }
        //参数 l1 和 r1 表示我们只截取了数组 arr1[l1...r1]这一部分元素,l2 和 r2 同
    public int findKth(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2, int k) {
        // 递归结束条件
      // l1 > r1,那么目标元素只可能在 arr2 中
        if(l1 > r1)
            return arr2[l2 + k - 1];
        if(l2 > r2)
            return arr1[l1 + k - 1];
        if (k <= 1)// 注意,k == 0的结束条件与上面两个结束条件不能颠倒。
            // 如果 k = 1,那么
            return Math.min(arr1[l1],arr2[l2]);
        int md1 = l1 + k/2 - 1 <= r1 ? l1 + k/2 - 1: r1;
        int md2 = l2 + k/2  - 1 <= r2 ? l2 + k/2 - 1: r2;
        if(arr1[md1] < arr2[md2])
            return findKth(arr1, md1 + 1, r1, arr2, l2, r2, k - (md1-l1+1));
        else
            return findKth(arr1, l1, r1, arr2, md2 + 1, r2, k - (md2-l2+1));
    }
}

对于这道题,还是挺难的,特别容易出错,如果你是新手,看不懂,那么可以先放着,后面在来看。

相关训练题

递归训练一:Leetcode 104.二叉树的最大深度

递归训练二:Leetcode 62.不同路径

递归训练三:剑指 Offer 16. 数值的整数次方

发表评论

后才能评论