求star

题目#

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

题解:key:#

①二分查找#

TIP

​ 注意此题要求复杂度为O(log(m+n))，所以合并排序的暴力解法是肯定行不通的，如果对时间复杂度的要求有log，通常都需要用到二分查找，这道题也可以通过二分查找实现。

​ 题目要求查找两个正序数组的中位数，则有两种情况:

• m + n 是奇数，那么直接返回最中间的一个元素
• m + n 是偶数，则需要计算中间两个元素的平均值

于是，寻找中位数的问题可以转化为 :arrow_right:寻找第K个小的元素。假设有序数组A和B，要找到第K个元素，我们可以比较A[k/2 - 1](由于数组下标从0开始所以要减1)和B[K / 2-1]的大小，其中 / 是整除。

通过比较可以归纳出三个情况:

1. A[k/2-1] < B[k/2-1]时，则比A[k/2 - 1]小的数最多只有A中的前k/2-1个数和B的前k/2-1个数，即最多有k-2个数比它小，所以A[k/2-1]不可能是第K个数，于是可以排除A[0]~A[k/2-1]
2. A[k/2-1] > B[k/2-1]时，同理可以排除B[0]~B[k/2-1]
3. A[k/2-1] = B[k/2-1],可以归纳到1中

此外，在比较的过程中，有三种特殊情况需要处理:

1. 当A[k/2-1]或A[k/2-1]越界时，可以选取对应数组的最后一个元素。所以，在这种情况下，不能直接将k减去k/2再继续迭代，而是必须根据排除数的个数减少K的值
2. 如果一个数组为空，说明其中的元素已经全部被排除，此时，就可以直接返回另一个数组中第K小的元素
3. 如果k==1,则只需要返回两个数组首元素的最小值即可

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
    const totalLen = nums1.length + nums2.length
    let median
    if (totalLen % 2 === 1) {	// 总共奇数个元素，则只需找到第K个元素即可
        let midIndex = Math.floor(totalLen / 2)
        median = getKthElement(nums1, nums2, midIndex + 1)
    } else {    // 总共有偶数个元素，需要找到中间两个数求平均值
        let midIndex1 = Math.floor(totalLen / 2) - 1, midIndex2 = Math.floor(totalLen / 2)
        median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2
    }
    return median
};
// 找到第K小的元素
const getKthElement = (nums1, nums2, k) => {
    const len1 = nums1.length, len2 = nums2.length
    let index1 = 0, index2 = 0
    while (1) {
        // 边界情况
        if (index1 === len1) {
            return nums2[index2 + k - 1]
        }
        if (index2 === len2) {
            return nums1[index1 + k - 1]
        }
        if (k === 1) {
            return Math.min(nums1[index1], nums2[index2])
        }
        // 普通情况
        let half = Math.floor(k / 2)
        let newIndex1 = Math.min(index1 + half, len1) - 1
        let newIndex2 = Math.min(index2 + half, len2) - 1
        let pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]
        if (pivot1 <= pivot2) {
            k -= (newIndex1 - index1 + 1)
            index1 = newIndex1 + 1
        } else {
            k -= (newIndex2 - index2 + 1)
            index2 = newIndex2 + 1
        }
    }
}