大家好！我是曾续缘🤣
今天是《LeetCode 热题 100》系列
发车第 68 天
二分查找第 6 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给定两个大小分别为 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
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10⁶ <= nums1[i], nums2[i] <= 10⁶
难度：💝💝💝

解题方法

这个问题是关于如何在两个已经排序的数组中找到中位数的问题。中位数是将一个集合划分为两个等长的子集，一个包含较小的元素，另一个包含较大的元素的元素。在这个问题中，我们有两个已经排序的数组，我们需要找到这两个数组合并后的中位数。

首先，我们需要理解的是，对于两个有序数组，中位数是两个数组中第 k 小的数，其中 k 依赖于两个数组的长度之和是奇数还是偶数。如果两个数组的长度之和是奇数，那么中位数就是第 (len1 + len2) / 2 小的数；如果长度之和是偶数，那么中位数是第(len1 + len2) / 2 小的数和第 (len1 + len2) / 2 + 1 小的数的平均值。

假设我们要找出这两个数组中的第 k 小元素。

为了公平地进行二分查找，我们从 num1 和 num2 中各选择最小的 k/2 个数，总共最多选取 k 个数。

如果 num1 中的前 k/2 个数中最大的数比 num2 中的前 k/2 个数中最大的数小，那么说明 num1 选中的这些数都比 num2 选中的最大数小。因此，这些来自 num1 的数不可能是第 k 个数，可以将其排除。然后我们可以减少 k，并继续这个过程。

这样通过逐步缩小范围，我们可以高效地找到这两个数组合并后的中位数。

Code

查看代码

java

class Solution {
    // 找到第k小的元素
    int findK(int[] nums1, int[] nums2, int k){
        int len1 = nums1.length, len2 = nums2.length;
        int p1 = 0, p2 = 0;
        while(true){
            // 如果p1已经到nums1的末尾，返回nums2中第k个元素
            if(p1 == len1) return nums2[p2 + k - 1];
            // 如果p2已经到nums2的末尾，返回nums1中第k个元素
            if(p2 == len2) return nums1[p1 + k - 1];
            // 如果k等于1，直接返回nums1和nums2中较小的一个
            if(k == 1) return Math.min(nums1[p1], nums2[p2]);
            // 每个数组向前移动k/2个元素，保证总移动个数不超过k，然后判断最终移动哪个k/2
            int mid1 = Math.min(p1 + k / 2 - 1, len1 - 1);
            int mid2 = Math.min(p2 + k / 2 - 1, len2 - 1);
            // 移动nums[mid]小的，因为可以判断它的k/2个元素不是答案要求的了
            if(nums1[mid1] <= nums2[mid2]){
                // 移动p1，减少k的值
                k -= mid1 - p1 + 1;
                p1 = mid1 + 1;
            }else{
                // 移动p2，减少k的值
                k -= mid2 - p2 + 1;
                p2 = mid2 + 1;
            }
        }
    }
    // 找到两个数组的中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        // 如果总长度是奇数，返回第(len+1)/2小的元素
        if(len % 2 == 1){
            return findK(nums1, nums2, (len + 1) / 2);
        }else{
            // 如果总长度是偶数，返回第len/2和第len/2+1小的元素的的平均值
            return (findK(nums1, nums2, len / 2) + findK(nums1, nums2, len / 2 + 1)) / 2.0;
        }
    }
}

解题方法 ​

Code ​

解题方法

Code