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

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

第一，中位数是一个有序序列中最中间的数，题目中的两个数组都是有序的，因此，如果已知一个数组中有多少个位于中位数左边，那么另一个数组位于中位数左边的数的数目也可以得知。下面将确定每个数组有多少数位于中位数左边的位置称作「划分点」。注意，这里说的中位数对于奇数个元素就是唯一的那一个，对于偶数个元素指的是较小的那个数。

第二，题目要求log时间复杂度，而两个数组都是有序的，因此可以考虑二分。

第三，中位数右边的数一定比左边的数大，因此按第一点提到的确定了两个数组的划分点后，右半部分的最小值必须不小于左半部分的最大值。如果不满足，可以排除数组一半的元素。

具体来说，二分其中一个数组（二分长度更小的数组时间更优），确定该数组中有多少数位于中位数左边，然后另一个数组也可以 确定有多少数位于中位数左边，通过检查是否满足「中位数右边的数不小于左边的数」，确定下次二分的范围。

代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 二分长度更小的数组
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        // 对于nums1数组，最多有m个位于中位数左边，最少0个
        int l = 0;
        int r = m;
        int max = Integer.MAX_VALUE;
        int min = Integer.MIN_VALUE;
        while (l <= r) {
            int i = l + (r - l) / 2;
            // 两个数组如果一共奇数个元素，需要找到第(m + n + 1) / 2个元素；
            // 如果是偶数，需要找到第(m + n) / 2和第(m + n) / 2 + 1个元素
            // 这里二分找的是较小的中位数，因此统一起来可以用(m + n + 1) / 2，减去i就是nums2中位于中位数左边的数目
            int j = (m + n + 1) / 2 - i;
            // right为第一个中位数(不包括自己)右边最小的数
            int right = Math.min(i < m ? nums1[i] : max, j < n ? nums2[j] : max);
            // left为第一个中位数(包括自己)左边最大的数
            int left = Math.max(i > 0 ? nums1[i - 1] : min, j > 0 ? nums2[j - 1] : min);
            if (left <= right) {
                // 当有奇数个元素，i-1和j-1中较大的数为中位数，当有偶数个元素，left和right共同组成中位数
                return (m + n) % 2 == 0 ? (left + right) / 2.0 : left;
            } else if (j > 0 && nums1[i] < nums2[j - 1]) {
                l = i + 1;
            } else {
                r = i - 1;
            }
        }
        return 0;
    }
}