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

题目描述

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

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

**输入：**nums1 = [1,3], nums2 = [2]
**输出：**2.00000
**解释：**合并数组 = [1,2,3] ，中位数 2

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

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• 106 <= nums1[i], nums2[i] <= 106

---

---

---

题解：

解法1 暴力（归并）

处理逻辑：

1. 合并 nums1，nums2 为第三个数组
2. 排序第三个数组
3. 按下标，找出中位数

因为 nums1 nums2 本身就是按从小到大排序好了的；
使用归并，一个一个地从 nums1 nums2 里面取出最小的数，放到第三个数组中。

代码如下：

• C++ 代码1

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), k = 0, i = 0, j = 0;
        vector<int> sub(m + n, 0);
        while (i < m && j < n)
            sub[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        while (i < m) sub[k++] = nums1[i++];
        while (j < n) sub[k++] = nums2[j++];
        return k % 2 ? sub[k / 2] : (sub[k / 2] + sub[k / 2 - 1]) / 2.0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

代码详细逻辑

1. 以 nums1 nums2 的大小来定义 第三个数组 sub（为合并做准备）。
2. 定义：
   • 指针 i，指向数组 nums1；
   • 指针 j，指向数组 nums2；
   • 指针 k，指向数组 sub。
3. while (i < m && j < n) 使用指针，每次从数组 nums1 nums2 选出当前最小那个数，合并到 sub 中，并同时 移动 选出了最小那个数的指针。
   需要注意，i j 2个指针不是同时移动的，那么总有一个会先移动到 “尾”；但是另一个指针还没有移动到 “尾”，而我们需要保证 nums1 nums2 两个数组里面所有的元素都合并到第三个数组 sub 中，所以有了接下来代码。
4. 我们只知道有一个 指针 移动到“尾”，但是 不知道 是哪一个指针移动到 “尾”，所以2个 指针 都分别做一个判断（也就是代码 while (i < m) 和 while (j < n)），并把 剩余 的数组元素，合并到 sub 中（也就是代码 sub[k++] = nums1[i++] 和 sub[k++] = nums1[j++]）。
5. 当合并完第三个数组后，我们再根据第三个数组的 大小 来选出 中位数。

时间复杂度：O(m + n)，完整的遍历了2个数组
空间复杂度：O(m + n)，申请了三个数组来装 nums1 nums2
（C++版本的代码是可以AC的，大家可以试试）

---

---

解法2 双指针

处理逻辑：

1. 申请2个指针，分别指向2个数组的头
2. 每次比较大小来移动 2个指针
3. 当指针移动的次数与 (m + n) / 2 相同时，得到中位数

注意边界问题：

2个指针在移动时，是否有超过2个数组的最大个数；
如果有，后续就只能移动另一个指针
1
2

先看一下代码：

• C++ 代码2

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        int m = nums1.size(), n = nums2.size(), i = 0, j = 0, l = 0, r = 0;
        for (int x = 0; x <= (m + n) / 2; x++) {
            l = r;
            r = (i < m && (j >= n || nums1[i] < nums2[j])) ?
                nums1[i++] : nums2[j++];
        }
        return (m + n) & 1 ? r : (l + r) / 2.0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

指针移动逻辑：

1. 定义2个指针 i j ，分别指向数组 nums1 nums2 的 “头”

nums1: 1 3 5 7 9 ... m
       ^ 指针 i

nums2: 2 4 6 8 10 ... n
       ^ 指针 j
1
2
3
4
5

1. 移动指针的条件：
   • 移动指针指向的数更小的那种指针
   • 一个指针已经指向了“尾”，只能移动另一个指针（逻辑上需要优先判断）
2. 指针移动 (m + n) / 2 + 1次

再看一下对应的代码：

r = (i < m && (j >= n || nums1[i] < nums2[j])) ? nums1[i++] : nums2[j++]
1

这是整合过的复合语句，看一下伪代码更容易让人理解：

if (i指针指到了“尾”) {
    只能移动 j 指针
} else if (j指针指到了“尾”) {
    只能移动 i 指针
} else {
    if (i指针指向的数 > j指针指向的数)
        移动 j 指针
    else
        移动 i 指针
}
1
2
3
4
5
6
7
8
9
10

---

---

解法3 二分查找

排序数组的中位数是由2个条件组成的；而只有一个数组情况，会因为本身的特殊性导致2个条件的重叠，而容易忽略另一个条件。

（以下条件都先默认数组的个数都是偶数的情况）

一个数组的情况

      left_A             |        right_A
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
1
2

找数组排序数组 A 的中位数：直接从中间位置切开 (m - 1) / 2 = i

那么就切成了2部分，并且左边的个数与右边的个数相同，也就是：
len(left_A) = len(right_A)

那么中位数就是 (A[i - 1] + A[i]) / 2
( 数组 A 的个数为奇数的情况同理： A[i] / 2 )

两个数组的情况

沿用一个数组的逻辑，我们可以先分别找到2个数组的中间位置。

      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
1
2
3

那么我们可以确实2件事：

1) len(left_part) == len(right_part)
2) max(A[i - 1], B[j - 1]) <= min(A[i], B[j])
1
2

但是中位数不一定是 max(A[i - 1], B[j - 1]) + min(A[i], B[j]) / 2

把两个数组当成一个数组

逻辑上合并的一个数组的中间位置是：(m + n) / 2

也就是在2个数组上，我们需要移到 i j 指针来保证无论什么时候都有：len(left_part) == len(right_part)
（也就是 i++ ，一定有 j-- ；i–，一定有 j++)

但是只能保证左右2边的个数相同，而这个位置取到的数不一定是中位数。
同时还需要 满足条件：

A[i - 1] < B[j] && B[j - 1] < A[i]
1

只有这样才能保证2个数组的左边部分都是小于右边部分，也就是：

max(left_part) <= min(right_part)
1

先看一下整体的代码：

• C++ 代码3

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), l = 0, r = m;
        if (m > n) return findMedianSortedArrays(nums2, nums1);
        while (l < r) {
            int i = (l + r) / 2, j = (m + n + 1) / 2 - i;
            nums1[i] < nums2[j - 1] ? l = ++i : r = i;
        }
        r = (m + n + 1) / 2 - l;
        int subL = max(l <= 0 ? INT_MIN : nums1[l - 1],
            r <= 0 ? INT_MIN : nums2[r - 1]);
        if ((m + n) & 1) return subL;
        int subR = min(l >= m ? INT_MAX : nums1[l],
            r >= n ? INT_MAX : nums2[r]);
        return (subL + subR) / 2.0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

细节问题1:中位数的抽象条件

上面提到了找排序数组的中位数，有2个条件，也就是切割位置要满足：

1、len(left) == len(right)
2、max(left) <= min(right)
1
2

找出这2个条件，套到2个数组，或者多个数组也是同样适用的。

细节问题2:边界问题

在做切割时数组会有如下三种情况：

|x x x x x
^ 切割位置

 x x x | x x x
       ^ 切割位置

 x x x x x x|
            ^ 切割位置
1
2
3
4
5
6
7
8

针对情况1:
切割位置左边没有值，我们伪造出一个 最小值 来代替。
因为左边部分我们是要找 最大值，给出假的最小值，不会影响到我们的判断

针对情况3:
切割位置右边没有值，我们伪造出一个 最大值 来代替。
因为右边部分我们是要找 最小值，给出假的最大值，不会影响到我们的判断

细节问题3: m <= n

规定数组A的长度小于等于数组B的长度，即 m <= n。这样对于任意的i，都有j = (m + n + 1) / 2 - i，
那么 j 一定是在[0, n)区间范围，不会出现负数的情况（减少状态处理）。

细节问题4: 只判断A[i] < B[j - 1]

上面我们说要满足：A[i - 1] < B[j] && B[j - 1] < A[i] （注意：这个是最终成立的2个条件，是并且关系）

而是要同时满足这2个条件，也就是说只要一个条件不满足我们就要重新查找新的条件。
那么分别针对2个条件单独做判断：

if (A[i - 1] < B[j]) {

    i向右移动
    j向左移动
} else {

    i向左移动
    j向右移动
}
-----------------------------------
if (B[j - 1] < A[i]) {

    i向右移动
    j向左移动
} else {

    i向左移动
    j向右移动
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

也就是说这 2个条件完全等价，我们在做判断的时候，只需要对一个条件做判断就行了。

细节问题5:二分查找的是什么

通过二分，我们可以快速切割出一半的数量。
而根据细节1中提到的，2边的数量要相同，很容易就算出别一个数组要出的数量。

那么接下来就是比较2个数组2边的取数是否满足：A[i - 1] < B[j] && B[j - 1] < A[i]

所以这里使用二分的目的就是：快速找到上面2个条件成立的位置。

细节问题6:j = (m + n + 1) / 2 - i

(m + n + 1) / 2 的目录是屏蔽掉奇数带来的影响。为什么可以这样：

如果：
m + n = 4 ; (m + n) / 2 = 2 ; (m + n + 1) / 2 = 2
m + n = 5 ; (m + n) / 2 = 2 ; (m + n + 1) / 2 = 3

也就是说：
如果 m + n 是偶数，那么 +1 不会影响到做 二分数 的切割。
如果 m + n 是奇数，那么 +1 会影响到做 二分数 的切割，但是只会是 len(left) - len(right) = 1；
也就是左边只会比右边多一个（中间位置数）
1
2
3
4
5
6
7
8

那么在做结果判断的时候，我们就需要对奇数先做判断就可以了。