⭐ 题目日期：

字节 - 2024/10/25

🌳 题目描述：

给定两个大小分别为 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

🕵🏽 面试评估：

考查二分查找，难度中等偏上

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

两个数组分别维护一个指针，初始指向索引 0，以某种规律向右移动，在合适的时机停在中位数上，返回结果。

指针单次跨越的元素越多，算法的效率越高。而一共要跨越多少元素，跟我们要找的元素位置有关。根据题意，要找中位数，通过简单的数学，能得到要找的具体位置为 k (0-based, 奇数在中间 k = n / 2, 偶数找中间两个(n / 2、n / 2 - 1)除以2, n 为数据总量)。

由于我们无法得知最小的 k 个数在两个数组内的分布情况。最激进的淘汰策略也只能在每个数组里选前 k / 2 个数，然后比较边界的大小, 较小的前 k / 2 个数被淘汰，并且能保证我们要找的第 k 个数不在淘汰的数据里，然后再更新指针的位置，因为已经淘汰的数不参与后续的比较。更新剩下需要淘汰/跨越的数量，递归重复以上步骤，直到某个数组里的数被淘汰完或者已经淘汰了足够的数 (base case)。

这道题对索引的精准掌控要求很高，这也是这道题的一个主要难点。我们要找的 k 是 0-based, 前 k / 2 个数的最后的数的索引为 index = left + (k - 1) / 2, 不是 left + k / 2, 其中 left 指向未淘汰数据部分的第一个数。举例说明：

A: [0, 1, 3]

B: [0, 2]

k = 5 / 2 = 2;

如果选用 left + k / 2， 则index1 = left1 + k / 2 = 1， index2 = left2 + k / 2 = 1;

而 nums[index1] < nums[index2], 根据我们的淘汰策略，A 中的 0，1 会被淘汰，而 1 是我们这道题的正确答案，所以 left + k / 2 是错的。

💻代码：

Java

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;
        if (totalLength % 2 == 1) {
            // 奇数情况，返回第 (totalLength / 2 + 1) 小的元素
            return findKthNum(nums1, nums2, 0, 0, totalLength / 2);
        } else {
            // 偶数情况，返回第 (totalLength / 2) 和 (totalLength / 2 + 1) 小元素的平均值
            int left = findKthNum(nums1, nums2, 0, 0, totalLength / 2 - 1);
            int right = findKthNum(nums1, nums2, 0, 0, totalLength / 2);
            return (left + right) / 2.0;
        }
    }

    private int findKthNum(int[] nums1, int[] nums2, int left1, int left2, int k) {
        // 边界情况
        if (left1 >= nums1.length) {
            return nums2[left2 + k];
        }
        if (left2 >= nums2.length) {
            return nums1[left1 + k];
        }
        if (k == 0) {
            return Math.min(nums1[left1], nums2[left2]);
        }

        // 计算两个数组中第 k/2 小的索引
        int newLeft1 = Math.min(left1 + (k - 1) / 2, nums1.length - 1);
        int newLeft2 = Math.min(left2 + (k - 1) / 2, nums2.length - 1);

        if (nums1[newLeft1] <= nums2[newLeft2]) {
            // 舍弃 nums1 中 [left1, newLeft1] 的部分
            return findKthNum(nums1, nums2, newLeft1 + 1, left2, k - (newLeft1 - left1 + 1));
        } else {
            // 舍弃 nums2 中 [left2, newLeft2] 的部分
            return findKthNum(nums1, nums2, left1, newLeft2 + 1, k - (newLeft2 - left2 + 1));
        }
    }

🚵🏻复杂度分析：

时间复杂度：log(m + n)

空间复杂度：log(m + n), 为递归栈的空间调用；也可以用迭代的方法找到 kth, 从而避免递归栈的调用

🔬在线评测(Online Judge):

题目链接