4-两个正序数组的中位数

LeetCode 4. Median of Two Sorted Arrays

LeetCode-4

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be $O(log (m+n))$.

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

method: 二分法

二分法只要出现l = mid，不管是在if分支还是在else分支，mid的计算都要用(l+r+1)/2

让nums1是短的那条，以防计算nums[j]的时候越界

知道了两个数组的大小，也就知道了合并后数组的中位数的位置，这里将偶数情况和奇数情况统一起来，都用(m + n + 1) / 2，让奇数情况的前半部分比后半部分多一个元素

问题转化为在nums1中寻找合适的分割点，使得两个数组分割点左侧的元素都小于分割点右侧的元素

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) swap(nums1, nums2);

    int m = nums1.size(), n = nums2.size();
    int totalLeft = (m + n + 1) / 2;
    int l = 0, r = m;
    while (l < r) {
        int i = l + r + 1 >> 1; // nums1分割点
        int j = totalLeft - i;  // nums2分割点
        if (nums1[i - 1] <= nums2[j]) l = i;    // 满足条件l右移
        else r = i - 1;     // 不满足条件r左移
    }
    int i = l;
    int j = totalLeft - i;
    // 四种极端情况
    int nums1Left = (i == 0) ? INT_MIN : nums1[i - 1];
    int nums1Right = (i == m) ? INT_MAX : nums1[i];
    int nums2Left = (j == 0) ? INT_MIN : nums2[j - 1];
    int nums2Right = (j == n) ? INT_MAX : nums2[j];
    if ((m + n) % 2) {  // 合并后是奇数
        return max(nums1Left, nums2Left);   // 两个数组左边较大值
    }
    else {  // 合并后是偶数
        return (max(nums1Left, nums2Left) + min(nums1Right, nums2Right)) / 2.0; // 左边较大值和右边较小值的平均
    }
}

极端情况

时间复杂度：$O(log{\rm min}(m, n))$
空间复杂度：$O(1)$