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

 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    }