4. 寻找两个正序数组的中位数

给定两个大小分别为 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^6 <= nums1[i], nums2[i] <= 10^6\)

思路

我们可以使用二分查找的方法来解决这个问题。具体步骤如下：

1. 确保 nums1 是较短的数组。如果不是，交换 nums1 和 nums2。
2. 设定两个指针 left 和 right，分别指向 nums1 的起始和结束位置。
3. 计算 halfLen，表示两个数组合并后左半部分的长度。
4. 在 nums1 上进行二分查找，计算分割点 i 和 j，其中 j = halfLen - i。
5. 检查分割点是否满足条件：
   • maxLeft1 <= minRight2 且 maxLeft2 <= minRight1
6. 如果满足条件，计算中位数：
   • 如果总长度为奇数，中位数为 max(maxLeft1, maxLeft2)。
   • 如果总长度为偶数，中位数为 (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0。
7. 如果不满足条件，调整 left 和 right 指针，继续二分查找，直到找到正确的分割点。

解答

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()>nums2.size())  return findMedianSortedArrays(nums2,nums1);

        int m = nums1.size();
        int n = nums2.size();
        int left = 0;
        int right = m;
        int halfLen = (m+n+1)/2;

        while(left<=right){
            int i = (left+right)/2;
            int j = halfLen - i;

            int maxLeft1 = (i==0)? INT_MIN:nums1[i-1];
            int minRight1 = (i==m)? INT_MAX:nums1[i];

            int maxLeft2 = (j==0)?INT_MIN:nums2[j-1];
            int minRight2 =(j==n)?INT_MAX:nums2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((m + n) % 2 == 1) {
                    return max(maxLeft1, maxLeft2);
                } else {
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
                }
            } else if (maxLeft1 > minRight2) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        return 0.0;
    }
};