LeetCode题解

题目：寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例1：

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例2：

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

解题思路：二分法

首先在做这题之前要了解什么是中位数，中位数作用：

中位数（又称中值，英语：Median），统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。

简而言之中位数把一个数集划分为长度相等两部分，而这个数要比上部分数值都要大，比下部分数值都要小

回过头来看题目要求，要求算法时间复杂度为O(log(m + n))，因此可以用二分法性质解决。

首先假设把A数组划分成任意(注意是任意，不是长度相等)两部分，A长度为m

                left                 |                 right
  A[0],A[1],A[2],.....A[i-2],A[i-1]  |  A[i],A[i+1],A[i+2]......A[m-1]

可以得出：lenA(left)=i,lenA(right)=m-i,同样把B数组划分任意两部分，B长度为n

                left                 |                 right
  B[0],B[1],B[2],.....B[j-2],B[j-1]  |  B[j],B[j+1],B[j+2]......B[n-1]

同理lenB(left)=j,lenB(right)=n-j,然后把A、B放进一个合集中

                left                 |                 right
  A[0],A[1],A[2],.....A[i-2],A[i-1]  |  A[i],A[i+1],A[i+2]......A[m-1]
  B[0],B[1],B[2],.....B[j-2],B[j-1]  |  B[j],B[j+1],B[j+2]......B[n-1]

我们可以先做一个假设:

1.如果len(left) = len(right)
2.根据1和中位数性质可以得出max(left) <= min(right)

那么现在把A、B并集划分为长度相等的两部分，要确保上述两个条件，只需要做到以下保证：

  • i+j = m-i+n-j，如果n>=m,只需保证0<=i<=m且j=(m+n+1)/2 - i(下面会解释为何不是j=(m+n)/2 - i)
  • A[i-1] <= B[j] && B[j-1] <= A[i]

首先为何n>=m？因为根据j=(m+n+1)/2 - i，m如果大于n且i有可能等于m的情况下j会变为负数，因此要保证n>=m

所以，在先不考虑边界条件的情况下证明了A[i-1] <= B[j] && B[j-1] <= A[i]就等于找到了完美的i就可以找到对应的中位数

因此可以根据二分法开始寻找：

1.假设iMin = 0,iMax = m, i = (iMin+iMax)/2, j = (m+n+1)/2 - i
2.根据len(left)=len(right),循环中会碰到三情况

  • i < iMax && B[j-1]>A[i] 证明i太小需要增大，当i增大时根据(m+n+1)/2 - ij就会减小，当i增j减时B[j-1]<=A[i]才有可能成立，因此重新定义区间，根据i = (iMin+iMax)/2，i要增大iMin也要增大,因此iMin=i+1,i=(iMin+iMax)/2进行二分查找

  • i > iMin && A[i-1]>B[j] 证明i太大需要减小，原理同上

  • 当上述两种情况都不出现时，证明找到了想要的i 这个时候判断m+n长度：
    如果为奇数则返回max(A[i-1],B[j-1]),偶数则返回(max(left)+min(right))/2

    而奇数为何是返回max(A[i-1],B[j-1])而不是max(A[i],B[i])呢

    这就需要回到前面j=(m+n+1)/2 - i，+1操作是m+n为奇数时：

    比如m+n=5,那么根据i+j=(m+n+1)/2后i+j(也就是len(left))=3，这个时候中位数就落在了左边

    而为什么要让中位数落在左边：

    因为根据代码实现，如果把中位数放在右边，那么相当于要返回min(A[i],B[j]),但实际上又存在边界条件，比如A=[],B=[1],这个时候len(right)是不存在的，因此min(A[i],B[j])就不存在，所以要选取len(left)存放中位数

  • 如果碰到i=0||i=m||j=0||j=m边界条件:

    • 假如i=0 || j=0，表示有一个左区间不存在，max(left)直接等于A[i]或B[j]
    • 同理i=m || j=n，表示有一个右区间不存在，min(right)直接等于A[i-1]或B[j-1]

代码实现

const findMedianSortedArrays = (A, B) => {
    let m = A.length,
        n = B.length;

    if (m > n) {
        [A, B] = [B, A]
        let temp = m;
        m = n;
        n = temp;
    }

    let iMin = 0, iMax = m, half = (m + n + 1) >> 1, i, j;

    while (iMin <= iMax) {
        i = (iMin + iMax) >> 1;
        j = half - i;
        if (i < iMax && B[j - 1] > A[i]) {
            iMin = i + 1
        } else if (i > iMin && B[j] < A[i - 1]) {
            iMax = i - 1
        } else {
            let maxLeft = 0;
            if (i === 0) {
                maxLeft = B[j - 1]
            } else if (j === 0) {
                maxLeft = A[i - 1]
            } else {
                maxLeft = Math.max(A[i - 1], B[j - 1])
            }

            if ((m + n) % 2 === 1) return maxLeft;

            let minRight = 0;
            if (i === m) {
                minRight = B[j]
            } else if (j === n) {
                minRight = A[i]
            } else {
                minRight = Math.min(A[i], B[j])
            }

            return (maxLeft + minRight) / 2
        }
    }
};

← 5.最长回文子串 →