问题描述

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

解题思路：

中位数是将有序数组分为两个长度相等的子数组，并且左侧子数组中的所有元素均小于右侧子数组中的所有元素。因此，本题可以转换为求两个有序数组中第 k 小的数。

假设两个有序数组分别为 nums1 和 nums2，我们需要找到第 k 小的数。首先，我们可以分别在 nums1 和 nums2 中找到第 k/2 小的数，分别记为 mid1 和 mid2。由于两个数组的元素个数不一定相等，因此我们不能保证 mid1 和 mid2 将两个数组分成长度相等的两个部分。但我们可以保证，mid1 和 mid2 将 nums1 和 nums2 分成的左侧部分的长度之和恰好为 k。

比较 mid1 和 mid2 的大小。如果 mid1 < mid2，则 nums1 中的左侧部分必定小于第 k 小的数，因此我们可以将其排除，继续在 nums1 的右侧和 nums2 中找第 k - k/2 小的数，于是将问题规模减少了一半。

当然，mid1 >= mid2 的情况也是类似的。

具体的算法流程如下：

1. 用 left 和 right 分别表示要查找的两个有序数组的左端和右端的下标，k 表示要查找的第 k 小的数，初始时，left 和 right 都为 0，k 为 (nums1 的长度 + nums2 的长度 + 1) / 2。

2. 在每一轮查找中，分别在 nums1 和 nums2 中查找第 k/2 小的数，分别记为 mid1 和 mid2，即 mid1 = nums1[(left + k/2 - 1) % nums1.length]，mid2 = nums2[(right + k/2 - 1) % nums2.length]。

3. 比较 mid1 和 mid2 的大小，如果 mid1 < mid2，则说明要查找的第 k 小的数位于 nums1 的右侧或 nums2 的左侧，我们可以将 left 设为 (left + k/2)，继续查找第 k - k/2 小的数。

4. 如果 mid1 >= mid2，则说明要查找的第 k 小的数位于 nums2 的右侧或 nums1 的左侧，我们可以将 right 设为 (right + k/2)，继续查找第 k - k/2 小的数。

5. 当 k = 1 时，我们只需要返回 nums1[left] 和 nums2[right] 中的较小值即可。

6. 如果两个数组的长度之和为奇数，则中位数为第 (nums1 的长度 + nums2 的长度 + 1) / 2 小的数，否则中位数为第 (nums1 的长度 + nums2 的长度) / 2 小和第 (nums1 的长度 + nums2 的长度) / 2 + 1 小的数的平均值。

下面是具体的代码实现：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLen = nums1.length + nums2.length;
        if (totalLen % 2 == 0) {
            // 如果总长度为偶数，则中位数为第 (nums1 的长度 + nums2 的长度) / 2 小和第 (nums1 的长度 + nums2 的长度) / 2 + 1 小的数的平均值
            int midIdx1 = totalLen / 2;
            int midIdx2 = midIdx1 + 1;
            return (getKth(nums1, 0, nums2, 0, midIdx1) + getKth(nums1, 0, nums2, 0, midIdx2)) / 2.0;
        } else {
            // 如果总长度为奇数，则中位数为第 (nums1 的长度 + nums2 的长度 + 1) / 2 小的数
            int midIdx = totalLen / 2 + 1;
            return getKth(nums1, 0, nums2, 0, midIdx);
        }
    }

    private int getKth(int[] nums1, int left1, int[] nums2, int left2, int k) {
        if (left1 >= nums1.length) {
            // 如果 nums1 已经查找完了，直接返回 nums2 中的第 k 个元素
            return nums2[left2 + k - 1];
        }
        if (left2 >= nums2.length) {
            // 如果 nums2 已经查找完了，直接返回 nums1 中的第 k 个元素
            return nums1[left1 + k - 1];
        }
        if (k == 1) {
            // 如果 k=1，直接返回 nums1 和 nums2 中的较小值
            return Math.min(nums1[left1], nums2[left2]);
        }
        int midIdx1 = left1 + k / 2 - 1;
        int midIdx2 = left2 + k / 2 - 1;
        int mid1 = midIdx1 >= nums1.length ? Integer.MAX_VALUE : nums1[midIdx1];
        int mid2 = midIdx2 >= nums2.length ? Integer.MAX_VALUE : nums2[midIdx2];
        if (mid1 < mid2) {
            // 如果 mid1 < mid2，则要查找的第 k 小的数位于 nums1 的右侧或 nums2 的左侧，递归查找第 k - k/2 小的数
            return getKth(nums1, midIdx1 + 1, nums2, left2, k - k / 2);
        } else {
            // 如果 mid1 >= mid2，则要查找的第 k 小的数位于 nums2 的右侧或 nums1 的左侧，递归查找第 k - k/2 小的数
            return getKth(nums1, left1, nums2, midIdx2 + 1, k - k / 2);
        }
    }
}