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

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;
    }