七七老师的白日梦

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

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

是什么？

数组中位数

怎么做？

二分法，因为要求了时间复杂度

思考

七七的想法其实是合并，因为刷了一道合并区间的题目，所以想到的是数组合并然后除以2然后一系列判断是否是中位数
‍
‍

import java.util.Arrays;

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] merged = new int[m + n];
//        将数组 nums1 从索引 0 开始，复制 m 个元素到数组 merged 中的起始位置（索引 0）。
        System.arraycopy(nums1, 0, merged, 0, m);
        System.arraycopy(nums2, 0, merged, m, n);
        Arrays.sort(merged);

        int total = m + n;
        if (total % 2 == 1) {
            return merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
}

但是这样子时间复杂度在m+n，不符合题目要求（力扣通过啦！），所以求助一下灵宝，得到如下

二分法

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
//定义分割点
        int m = nums1.length;
        int n = nums2.length;
        int low = 0;
        int high = m;
//开启循环，寻找使得两个数组划分后的元素满足交叉小于等于的条件，从而找到中位数
        while (low <= high) {
//            low+high  / 2本质上是对nums1取整，所以会得到一个整数，
            int partition1 = (low + high) / 2;
//         partiti1会不断变化，为减少计算，直接把partiti2与partition1相连接，减少计算，
//            原理一样，计算中位数，加1是为了处理奇数个的情况
            int partition2 = (m + n + 1) / 2 - partition1;
//Integer.MIN_VALUE 是 Java 中的最小整数值，用于表示一个极小的边界值，
// 确保在数组没有左半部分的情况下，逻辑仍然正确。
            int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
            int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
//因为正序排序，所以最大值在左边，最小值在右边，这里是判断分割点是否合适，取值
            int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
            int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
//保证连续性，确保分割点在两个数组中都存在
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // 找到合适的分割点
                if ((m + n) % 2 == 0) {
//                    联想中位数的定义，中位数是两个数之和除以2，这里找分割点两边的数之和除以2，得到中位数
                    return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
                } else {
//                    因为排序过了，可以想象一个数轴，左边的数比右边的数小，所以左边的数轴向右移动，右边的数轴向左移动
                    return Math.max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                // 向左移动
                high = partition1 - 1;
            } else {
                // 向右移动
                low = partition1 + 1;
            }
        }

        return -1;
    }
}

‍有时候也会想七七是不是笨蛋，这道题也花了差不多两个小时，最后想明白了。。。。不难嘛！可能自己也是大笨蛋吧。