Leetcode 4 寻找两个正序数组的中位数 ( Median of Two Sorted Arrays *Hard* ) 题解分析

题目介绍

给定两个大小分别为 mn 的正序(从小到大)数组 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

分析与题解

这个题也是我随机出来的,之前都是随机到 easy 的,而且是序号这么靠前的,然后翻一下,之前应该是用 C++做过的,具体的方法其实可以从他的算法时间复杂度要求看出来,大概率是要二分法这种,后面就结合代码来讲了

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        if (n1 > n2) {
            return findMedianSortedArrays(nums2, nums1);
        }

        // 找到两个数组的中点下标
        int k = (n1 + n2 + 1 ) / 2;
        // 使用一个类似于二分法的查找方法
        // 起始值就是 num1 的头跟尾
        int left = 0;
        int right = n1;
        while (left < right) {
            // m1 表示我取的是 nums1 的中点,即二分法的方式
            int m1 = left + (right - left) / 2;
            // *** 这里是重点,因为这个问题也可以转换成找成 n1 + n2 那么多个数中的前 (n1 + n2 + 1) / 2 个
            // *** 因为两个数组都是排好序的,那么我从 num1 中取了 m1 个,从 num2 中就是去 k - m1 个
            // *** 但是不知道取出来大小是否正好是整体排序的第 (n1 + n2 + 1) / 2 个,所以需要二分法上下对比
            int m2 = k - m1;
            // 如果 nums1[m1] 小,那我在第一个数组 nums1 的二分查找就要把左端点改成前一次的中点 + 1 (不然就进死循环了
            if (nums1[m1] < nums2[m2 - 1]) {
                left = m1 + 1;
            } else {
                right = m1;
            }
        }

        // 因为对比后其实我们只是拿到了一个位置,具体哪个是第 k 个就需要继续判断
        int m1 = left;
        int m2 = k - left;
        // 如果 m1 或者 m2 有小于等于 0 的,那这个值可以先抛弃
        // m1 如果等于 0,就是 num1[0] 都比 nums2 中所有值都要大
        // m2 等于 0 的话 刚好相反
        // 可以这么推断,当其中一个是 0 的时候那么另一个 mx 值肯定是> 0 的,那么就是取的对应的这个下标的值
        int c1 = Math.max( m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1] , m2 <= 0 ?  Integer.MIN_VALUE : nums2[m2 - 1]);
        // 如果两个数组的元素数量和是奇数,那就直接可以返回了,因为 m1 + m2 就是 k, 如果是一个数组,那这个元素其实就是 nums[k - 1]
        // 如果 m1 或者 m2 是 0,那另一个就是 k,取 mx - 1的下标就等于是 k - 1
        // 如果都不是 0,那就是取的了 nums1[m1 - 1] 与 nums2[m2 - 1]中的较大者,如果取得是后者,那么也就是 m1 + m2 - 1 的下标就是 k - 1
        if ((n1 + n2) % 2 == 1) {
            return c1;
        }
        // 如果是偶数个,那还要取两个数组后面的较小者,然后求平均值
        int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) / 2.0;
    }

前面考虑的方法还是比较繁琐,考虑了两个数组的各种交叉情况,后面这个参考了一些网上的解法,代码比较简洁,但是可能不容易一下子就搞明白,所以配合了比较多的注释。