菜园前端

Appearance

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

原文题目

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

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

https://leetcode.cn/problems/median-of-two-sorted-arrays/description/

题目分析 ​

题目中的意思就是给你两个已经排好序的数组，你需要找到他们中间的那个数。例如 nums1 = [1, 3, 5]，nums2 = [2, 4, 6, 8]，可以把这些数合并起来，并且排好序是这样的 1 2 3 4 5 6 8，这组数的中位数就是 4。

还有一种特殊的情况，两个数组的总长度是偶数，它们合并之后是这样的 1 2 3 4 5 6 8 10，那么中位数就是 4 和 5 之间，也就是 4.5。

题解思路 ​

方式一：直接合并数组并排序 ​

有的同学可能就会想到了，这不是很简单吗？遍历两个数组，将它们合并为一个数组，然后在进行排序。

这样确实可以，但是时间复杂度不满足题目要求。当你进行遍历和排序的时候，代码最优的的情况下，时间复杂度也要 O(m + n)，而题目要求的是 O(log (m+n))。

时间复杂度：O(m + n)

空间复杂度：O(m + n)

方式二：通过二分搜索算法实现 ​

注意

在菜园前端笔记中，有介绍到二分搜索的算法，如需要回顾可以跳转回去。

什么是二分搜索？

js
const findMedianSortedArrays = function (nums1, nums2) {
    const m = nums1.length
    const n = nums2.length

    let low = Math.floor(m / 2)
    let high = Math.floor((m + n) / 2) - low

    while ((low) => 0 && low <= m && high >= 0 && high <= n) {
        const min1 = nums1[low - 1] ?? -Infinity
        const max1 = nums1[low] ?? Infinity
        const min2 = nums2[high - 1] ?? -Infinity
        const max2 = nums2[high] ?? Infinity

        if (min1 <= max2 && min2 <= max1) {
            if ((m + n) % 2 === 1) {
                return Math.min(max1, max2)
            }

            if ((m + n) % 2 === 0) {
                return (Math.max(min1, min2) + Math.min(max1, max2)) / 2
            }

            break
        }

        if (min2 > max1) {
            low++
            high--
            continue
        }

        if (min1 > max2) {
            low--
            high++
            continue
        }
    }
}

const res = findMedianSortedArrays([1, 3, 5], [2, 4, 6, 8, 10])
const findMedianSortedArrays = function (nums1, nums2) {
    const m = nums1.length
    const n = nums2.length

    let low = Math.floor(m / 2)
    let high = Math.floor((m + n) / 2) - low

    while ((low) => 0 && low <= m && high >= 0 && high <= n) {
        const min1 = nums1[low - 1] ?? -Infinity
        const max1 = nums1[low] ?? Infinity
        const min2 = nums2[high - 1] ?? -Infinity
        const max2 = nums2[high] ?? Infinity

        if (min1 <= max2 && min2 <= max1) {
            if ((m + n) % 2 === 1) {
                return Math.min(max1, max2)
            }

            if ((m + n) % 2 === 0) {
                return (Math.max(min1, min2) + Math.min(max1, max2)) / 2
            }

            break
        }

        if (min2 > max1) {
            low++
            high--
            continue
        }

        if (min1 > max2) {
            low--
            high++
            continue
        }
    }
}

const res = findMedianSortedArrays([1, 3, 5], [2, 4, 6, 8, 10])

时间复杂度：O(log (m + n))

空间复杂度：O(1)

思路分析

  1. 其实可以将两个数组，想象为一个数组，只需要在这个数组中间切一刀，就能找到中位数。

  2. 当然，我们现在是两个数组 nums1 = [1, 3, 5] 和 nums2 = [2, 4, 6, 8, 10]。那只能在每个数组的中间切一刀，然后分割的部分挪动到合适的位置即可。

  3. 首先在第一个数组中间切一刀。因为数组的长度是奇数，所以这一刀就切在中间的前面一点。

  1. 然后在第二个数组中间也切一刀。因为第一个数组是切的是偏前一点的，所以第二个数组切的时候就偏后一点。
  1. 这样左侧的数量为 4 ，右侧的数量也为 4，两边比较平衡，不会偏差很大。
  1. 当 min1 小于等于 max2 并且 min2 小于等于 max1 的时候，左侧的部分刚好就是合并成一个数组后的左侧部分，右侧则是合并成一个数组后的右侧部分。
  1. 如果不符合以上判断，则需要调整两个数组的分割线。目前 min1 小于等于 max2 是成立的，所以不需要进行操作。但是 min2 并不小于等于 max1，所以数组 nums1 的分割线往右边挪一格，数组 nums2 的分割线则往左边挪一格。

  1. 这个时候两边的判断条件都成立了。我们来验证一下，假设数组合并排序之后为 [1, 2, 3, 4, 5, 6, 8, 10]。那么 1 2 3 4 是不是为中位数的左侧部分，5 6 8 10 是不是为中位数右侧的部分。所以最后当判断条件成立时，只需要直接求中位数即可。

  2. 如果合并后的数组长度是偶数，那么中位数就是 Math.max()

更新时间: