【递归打卡3】求两个有序数组的中位数(论思维转换的重要性)

【题目】

给定两个有序数组arr1和arr2，已知两个数组的长度分别为 m1 和 m2，求两个数组中的中位数。要求时间复杂度O(log(m1 + m2))。

【举例】

例如 arr1 = [1, 3]，arr2 = [2].

则中位数为 2.

例如 arr1 = [1,2]，arr2 = [3,4].

则中位数是 (2 + 3)/2 = 2.5

【难度】

难

解答

没看过这两道题的建议先搞懂这两道题：

这道题和我上两次讲的那两道题是非常相似的，不过这道题比上面两道题要难很多，大家可以先想想怎么做这道题哦。

为什么说它难呢？其实是有原因的，如果两个数组的长度和为奇数的话，那么这道题不难，它比“求两个有序数组的第 K 小数”还简单；难就难在两个数组的长度和为偶数时，这道题的难度顿时上升了。

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

那怎么办呢？实际上，这道题我们是可以进行一下转换，就是无论两个数组的长度和是奇数还是偶数，我们都求出第 （m1+m2+1)/2 小数以及第 （m1+m2+2)/2小数，然后求这两个数的平均数，就可以了。这样，我们就屏蔽了奇偶数的影响，会容易了挺多，并且可以利用我们上次写的”求两个有序数组的第 K 小数“来解决，这就是问题转换的重要性，要善于把复杂度的题转化为我们比较熟悉的题，才能举一反三。

代码如下：

 1    // 由于中位数会受长度是奇偶数的影响，所以我们可以把问题转化为求
 2    // (（n+m+1)/2+(n+m+2)/2)/2。
 3    public double findMedianSortedArrays(int[] arr1, int[] arr2) {
 4        int n = arr1.length;
 5        int m = arr2.length;
 6        return (findKth(arr1, arr2,(n+m+1)/2) + findKth(arr1,arr2,(n+m+2)/2)) /2;
 7    }
 8
 9    public static int findKth(int[] arr1, int[] arr2, int k) {
10        if(arr1 == null || arr1.length < 1)
11            return arr2[k-1];
12        if(arr2 == null || arr2.length < 1)
13            return arr1[k-1];
14        // 注意这个函数的参数有7个，上面那个函数的参数只有3个，同名不同函数哈
15        return findKth(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k - 1);
16    }
17
18    public static int findKth(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2, int k) {
19        // 递归结束条件
20        if(l1 > r1)
21            return arr2[l2 + k];
22        if(l2 > r2)
23            return arr1[l1 + k];
24        if (k == 0)// 注意，k == 0的结束条件与上面两个结束条件不能颠倒。
25            return Math.min(arr1[l1],arr2[l2]);
26        int md1 = l1 + k/2 < r1 ? l1 + k/2 : r1;
27        int md2 = l2 + k/2 < (r2 - l1) ? l2 + k/2 : r2;
28        if(arr1[md1] < arr2[md2])
29            return findKth(arr1, md1 + 1, r1, arr2, l2, r2, k - k / 2 - 1);
30        else if (arr1[md1] > arr2[md2])
31            return findKth(arr1, l1, r1, arr2, md2 + 1, r2, k - k / 2 - 1);
32        else
33            return arr1[md1];//返回arr2[md2]也可以，一样的。
34    }

`
这三道递归的题可以说是后一道是前一道的进阶，虽然思路上不怎么难，但要实现出来还是有一定的难度，如果你都搞懂了，并且自己把代码写出来了，对你编写代码的能力一定会大大提升。

推荐阅读