4. Median Of Two Sorted Arrays #

题目 #

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.

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

思路 #

朴素做法 #

这道题的朴素做法自然是合并两个有序数组，然后计算中位数，不过这样时间复杂度就达到了O(m+n)，不符合题目要求，那么自然地就会考虑二分法。

二分需要满足两个条件，单调和唯一。那么如何把题目转换成符合二分的形式呢？

中位数到数组划分 #

假设我们已经将两个数组合并成了一个有序数组，那么我们考虑一个划分，将整个数组从中间分开划分为大小两个部分，保证小的部分的个数满足⌊(m + n) / 2⌋。

通过这个划分，我们可以很快得到中位数的计算：

• 如果总数是奇数，那么中位数就是大的部分中最小值；
• 如果总数是偶数，那么中位数就是小的部分中最大值和大的部分中最小值的平均值；

这里我们可以看到，奇数偶数的影响已经被放到了最后一步，前面我们可以统一地考虑如何找到这个划分。

整体划分到单个数组的划分 #

首先，我们需要将这个划分，从一个合并数组的划分转换为两个单独有序数组的两个划分。这里我们考虑小的部分。

小的部分里的元素可能来源于两个数据，或者nums1，或者nums2，将他们按来源分开成两个部分，就能对应上原来两个数据两个划分。同时，最关键的是：

如果nums1的划分确定了，nums2的划分也可以唯一确定，因为两个部分的元素数量是固定的。

所以问题就转换成了，在nums1里找到一个划分，计算nums2里对应的划分，看是否满足：nums1和nums2小的部分的元素都小于等于大的部分的元素。

二分查找 #

这个划分是单调的吗？显然是的。随着划分从小的位置往大的位置移动，小的部分里的元素逐渐增多，直到等于需要的⌊(m + n) / 2⌋，且一定有解且唯一。

那么二分时如何检验一个划分是否合理，以及往哪个方向调整呢？

为了方便讨论，我们用实线表示最终需要的划分，用虚线表示二分法待检查的划分，记为实线1，实线2，虚线1，虚线2。

同时，记实线前最大元素为s，实线后最小元素为t，虚线前最大元素为a，虚线后最大元素为b，对应两个数组，我们有，s1, t1, s2, t2, a1, b1, a2, b2满足：

1. s1 <= t1
2. s2 <= t2
3. s1 <= t2
4. s2 <= t1
5. a1 <= b1
6. a2 <= b2

其中，3和4是因为实线将数组分为了大小两个部分，左边的元素都小于等于实线右边的元素。所以，如果这个划分是准确的，那么a1 = s1, b1 = t1, a2 = s2, b2 = t2, 那么我们应该有：

1. a1 <= b2
2. a2 <= b1

如果虚线1的位置偏小(a1 <= b1 <= s1 <= t1)，因为划分的元素个数固定，则导致虚线2的位置偏大(s2 <= t2 <= a2 <= b2)，那么会导致：

b1 <= s1 <= t2 <= a2

同理，如果虚线1的位置偏大(s1 <= t1 <= a1 <= b1)，因为划分的元素个数固定，则导致虚线2的位置偏小(a2 <= b2 <= s2 <= t2)，那么会导致：

b2 <= s2 <= t1 <= a1

注意，这里可能同时出现 b1 <= a2, b2 <= a1吗？不可能，因为：

b1 >= a1 >= b2 >= a2 矛盾

至此，我们得出了一个通过二分法找到目标划分的方式，通过最开始提到的转换，即可算出两个有序数组的中位数。

注意，我们可以二分查找元素数目较少的数组划分，一来可以减少查找次数，二来如果查找元素数目较多的数组划分，通过计算得到另一个数组的划分可能是不合法的。例如上图，如果红色数组枚举到了最右侧的位置，计算出来黄色数组应该在-1的位置划分，这就需要额外的特殊处理了。

代码 #

use std::cmp;
impl Solution {
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        if nums1.len() < nums2.len() {
            Self::find_median_in_smaller_sorted_arrays(&nums1, &nums2)
        } else {
            Self::find_median_in_smaller_sorted_arrays(&nums2, &nums1)
        }
    }

    fn find_median_in_smaller_sorted_arrays(nums1: &Vec<i32>, nums2: &Vec<i32>) -> f64 {
        let n = nums1.len();
        let m = nums2.len();

        let total = n + m;
        let lower_bound = total / 2;

        // range in 0..n
        let mut l = 0;
        let mut r = n; 
        while l < r {
            let m1 = (l + r ) / 2;
            let m2 = lower_bound - m1;

            if m2 > m || (m2 > 0 && m1 < n && nums1[m1] <= nums2[m2 - 1]) {
                l = m1 + 1;
            } else {
                r = m1;
            }
        }

        let m1 = l;
        let m2 = lower_bound - m1;

        if Self::is_odd(total) {
            return Self::find_least(&nums1, &nums2, m1, m2) as f64;
        } else {
            return (Self::find_most(&nums1, &nums2, m1, m2) + Self::find_least(&nums1, &nums2, m1, m2)) as f64 / 2.0;
        }
    }

    fn is_odd(len: usize) -> bool {
        return len&1 != 0;
    }

    fn find_least(nums1: &Vec<i32>, nums2: &Vec<i32>, m1: usize, m2: usize) -> i32 {
        if m1 == nums1.len() {
            return nums2[m2];
        }

        if m2 == nums2.len() {
            return nums1[m1];
        }

        return cmp::min(nums1[m1], nums2[m2]);
    }

    fn find_most(nums1: &Vec<i32>, nums2: &Vec<i32>, m1: usize, m2: usize) -> i32 {
        if m1 == 0 {
            return nums2[m2 - 1];
        }

        if m2 == 0 {
            return nums1[m1 - 1];
        }

        return cmp::max(nums1[m1 - 1], nums2[m2 - 1]);
    }


}

附录 #

图片是用excalidraw绘制的。