【每日一题 - LeetCode 热题 HOT 100 - 4. 寻找两个正序数组的中位数】

题目

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 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

思路一

第一种思路大家肯定都能想到，就是先用数组排序，然后在求中位数。如果不看题目要求的时间复杂度，那么我们可以有很多种解法，因为数组排序就有很多种时间复杂度，简单列举两种解题思路。

1. O(n^2)复杂度
   这里大家应该都知道了，直接用数组拼接就可以实现。代码如下：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1Length = nums1.length;
        int nums2length = nums2.length;

        nums1 = Arrays.copyOf(nums1, nums1Length+nums2length);//数组扩容
        System.arraycopy(nums2, 0, nums1, nums1Length, nums2length);

        Arrays.sort(nums1);
        if (nums1.length % 2 == 0){
            return (nums1[nums1.length/2] + nums1[nums1.length/2 - 1])/2.0;
        }else{
            return nums1[(int)(nums1.length/2.0 - 0.5)];
        }
    }

2.O(m+n)复杂度
看到这个复杂度大家应该也知道是什么数组合并方法，就是归并(Merge)合并。由于给定的两个数组是有序的，所以只需要判定元素间大小即可排序，代码如下：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0 && nums2.length == 0) {
            return 0.0;
        }
        int nums1Index = 0;
        int nums2Index = 0;
        int[] newArrays = new int[nums1.length + nums2.length];
        int newArraysIndex = 0;
        while (nums1Index < nums1.length && nums2Index < nums2.length) {
            if (nums1[nums1Index] <= nums2[nums2Index]) {
                newArrays[newArraysIndex++] = nums1[nums1Index];
                nums1Index++;
            } else {
                newArrays[newArraysIndex++] = nums2[nums2Index];
                nums2Index++;
            }
        }
        if (nums1Index == nums1.length) {
            while (nums2Index < nums2.length) {
                newArrays[newArraysIndex++] = nums2[nums2Index];
                nums2Index++;
            }
        } else {
            while (nums1Index < nums1.length) {
                newArrays[newArraysIndex++] = nums1[nums1Index];
                nums1Index++;
            }
        }

        int h = newArrays.length % 2;
        if (h == 0) {
            return ((double) newArrays[newArrays.length / 2] + newArrays[newArrays.length / 2 - 1]) / 2;
        } else {
            return newArrays[newArrays.length / 2];
        }
    }

思路二

其实从上面两种方法的时间复杂度来说，都不满足题目要求的O(log (m+n))。其实我们可以想想，合并数组并不是必要的，我们只需要找到两个有序数组中间的那个数字就可以了。例如，如果是[1,2,3]和[3,4,5]，我们就知道中位数是3。同时从时间复杂度来看，题目要求我们使用二分的方式。
题目可以抽象为找第k小的数字，比如上面的例子中，就是找第3小的数字。那么就可以在两个数组中做对比，假如中位数指数是6，也就是要找第6小的数字。因为是两个数组，首先取6的一半也就是3，两个数组的第3位作比较，小的那个数组之前的就都不符合要求，可以直接去掉，那么也就变成了找第3小的数字。同样的方法，取3的一半是1.5，也就是1，找到两个数组中的第1位数字进行比较，小的那部分去掉。最终我们可以找第1小的数字，这个时候就是看两个数字中的第一位谁更小了。

代码如下:

private static int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k){
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end2, k);
        if (len1 == 0) return nums2[start2 + k -1];
        //接近中位数
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;
        //如果nums1更大，说明nums2前面部分可以不要了
        if (nums1[i] > nums2[j]){
            return getKth(nums1, start1, end1, nums2, j+1, end2, k-(j - start2 + 1));
        }else{
            return getKth(nums1, i+1, end1, nums2, start2, end2, k-(i - start1 + 1));
        }
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int n = nums1.length;
        int m = nums2.length;

        int left = (n+m+1) / 2;
        int right  = (n + m + 2) / 2;
        return (getKth(nums1, 0, n-1, nums2, 0, m-1 ,left) + getKth(nums1, 0, n-1, nums2, 0, m-1 ,right)) * 0.5;
    }

参考

1. https://leetcode.cn/problems/median-of-two-sorted-arrays/