Skip to content

Latest commit

 

History

History
100 lines (96 loc) · 2.84 KB

004.寻找两个有序数组的中位数.md

File metadata and controls

100 lines (96 loc) · 2.84 KB
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

示例

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

思路

中位数会将一个有序分为两部分， 且两部分的个数相等。
现在有两个有序数组A、B，长度分别书 m 和 n，假设左边A的个数为 i，B 的个数 j，如下：

左边 右边
A[0],...,A[i-1] A[i],...,A[m-1]
B[0],...,B[j-1] B[j],...,B[n-1]

则可以得到公式如下:

$$i + j = (m + n + 1) / 2; 0 <= i <= m ; => j = (m + n + 1) / 2 - i; A[i-1] <= B[j];B[j-1] <= A[i]; midan = (max(left) + min(right)) / 2;$$

说明：
(m + n + 1)而不是(m + n)是因为当出现m+n为奇数时，保证中位数在左边。
保证n >= m，否则 j 会出现负数。

在0-m的范围对i进行二叉树搜索，会出现三种情况：

  • B[j - 1] <= A[i] && A[i - 1] <= B[j]:
    找到了i，停止搜索
  • B[j - 1] > A[i]:
    继续增加iMin
  • A[i - 1] > B[j]:
    继续减小iMax

解题代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
let findMedianSortedArrays = function(nums1, nums2) {
    let m = nums1.length;
    let n = nums2.length;
    // 保证n >= m
    if (m > n) {
        let temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        temp = m;
        m = n;
        n = temp;
    }
    let iMin = 0, iMax = m, halfLen = Math.ceil((m + n) / 2);
    // 二分查找i，使i满足终止条件
    while (iMin <= iMax) {
        let i = Math.floor((iMin + iMax) / 2);
        let j = halfLen - i;
        if (i < iMax && nums2[j - 1] > nums1[i]) {
            iMin = i + 1;
        }
        else if (i > iMin && nums1[i - 1] > nums2[j]) {
            iMax = i - 1;
        }
        else {
            let maxLeft = 0;
            if (i === 0) {
                maxLeft = nums2[j - 1];
            }
            else if (j === 0) {
                maxLeft = nums1[i - 1];
            }
            else {
                maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
            }
            // 奇数时直接返回中间值
            if ((m + n) % 2 === 1) {
                return maxLeft;
            }
            // 偶数时计算两数的平均值
            let minRight = 0;
            if (i === m) {
                minRight = nums2[j];
            }
            else if (j === n) {
                minRight = nums1[i];
            }
            else {
                minRight = Math.min(nums1[i], nums2[j]);
            }
            return (maxLeft + minRight) / 2;
        }
    }
    return 0;
};