LeetCode实战004 寻找两个有序数组的中位数

2019-05-10 本文已影响0人 Rooooyy

题目描述

给定两个大小为 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

题目解析

解决这个问题，我们必须要搞清楚两个问题：

两个数组都是有序数组，数组的元素都是从小到大排列的
中位数的定义：在中学数学中，我们可能学习过中位数的定义，但在统计学中，中位数还有这样一种解释：

中位数：当一个数可以将一个集合划分成两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素，那么这个数就称为集合的中位数。

这个题目的难点在于，给你一个有序数组，你肯定会求中位数。给你两个数组，你肯定也能想办法用暴力法解出来，但暴力求解，复杂度一定是超过 $O(log(m+n))$ 的！

这个题目是查找两个有序数组的中位数，我们能想到的 $O(log(...))$ 级别的查找算法，恐怕只有二分查找了。

二分查找法是用于解决一个数组的查找问题的，那么如何解决两个数组的问题呢？还是有一些情况需要讨论！

解法：二分查找法

从前面中卫数的定义来看，我们的出发点，应该是划分而不是遍历。

那么具体应怎么划分呢？假设有两个有序数组A、B，长度分别为m、n:

首先，让我们在任一位置 $i$ 将 $A$ 划分成两个部分（注意A[i]在右边这个集合）：

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

不难得出： $len(left\_A)=i, len(right\_A)=m-i, i \in [0, m]$

同样我们在位置 $j$ 对 $B$ 进行划分：

          left_B             |        right_B
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

同理： $len(left\_B)=j, len(right\_B)=n-j, j \in [0, n]$

将两个数组的左右部分都合并起来，形成总体的两个左右子集：

          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]

如果i和j的取值足够合适，使得：

$len(left\_part) = len(right\_part)$

$max(left\_part) \le min(right\_part)$

那么我们就可以找到这个中位数，它就等于:
$\frac{max(left\_part)+min(right\_part)}2$

上面的两个条件，等价于：

$i+j=m-i+n-j \Rightarrow j=\frac{m+n}2$
$B[j-1] \le A[i], A[i-1] \le B[j]$

这里有几点需要说明：

这里我们假设 $A[i-1], B[j-1], A[i], A[j]$ 始终存在，也就是说 $i \notin \{0, m\}, j \notin \{0, n\}$ , 这种极端情况我们最后来讨论

这里设 $n \ge m$ ，因为 $i, j$ 都必须是非负数，且 $j = \frac{m+n+1}2 - i$ , 当 $n \lt m$ 时，左边的表达式有可能小于0

条件2中的两个子条件，不可能同时不满足，请自己思考原因

所以，我们的任务就是：

在 $[0, m]$ 中搜索 $i$ ，使得 $B[j-1] \le A[i], A[i-1] \le B[j]$ , 其中 $j=\frac{m+n+1}2-i$

现在，我们已经把一个双数组遍历问题，变成了对一个变量的搜索问题！

接下来，我们来具体设计我们的二分算法：

设 $imin=0, imax=m$ ，它们夹成了一个 $i$ 的初始搜索区间
在二分查找法中，被查找的 $i$ 应该赋予这个区间的中值，即 $i=\frac{imin+imax}2$ , 那么 $j$ 也可以根据 $j = \frac{m+n+1}2$ 求得一个值
现在我们来检查上面的条件2是否满足，一共有3种情况：
- $B[j-1] \le A[i], A[i-1] \le B[j]$ 这表明 $i$ 已经搜索到了目标值，结束搜索
- $B[j-1] \gt A[i]$ ：这意味着 $i$ 太小了，目标值应该在 $[i+1, imax]$ 之间，因此设 $imin=i+1$ ，返回步骤2
- $A[i-1] \gt B[j]$ ：这意味着 $i$ 太大了，目标值应该在 $[imin, i-1]$ 之间，因此设 $max = i-1$ ，返回步骤2

最后，我们来讨论一下刚才忽略的临界情况：

这里我们要证明一下 $i$ 与 $j$ 的取值关系

由于 $n \ge m$ ,

$i \le m \Rightarrow j = \frac{m+n}2 - i \ge \frac{2m}2 - i \ge 0$ , 当且仅当 $i=m$ 时， $j =0$

同理可证 $i \ge 0 \Rightarrow j \le n$ , 当且仅当 $i = 0$ 时， $j=n$

这意味着，在判断临界情况时，我们只需关心 $i$ 的取值， $i$ 为临界值， $j$ 也一定取临界值

还意味着， $A[i-1], B[j-1]$ 必然有一个是存在的， $A[i], B[j]$ 也必然有一个是存在的！

还没完！

现在我们只是找到了最佳划分，还没有搞清楚哪个值是中位数！

现在，我们已经把A和B划分成了合适的left_part和right_part两个子集

      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]

那么，中位数只能在 $max(left\_part)$ 和 $min(right\_part)$ 中产生

由于 $j = \frac{m+n}2-i$ ，且在C++中，整数除法会舍弃小数，向下取整。

当 $m+n$ 为奇数的时候，虽然我们的条件 $j = \frac{m+n}2-i$ 使得 $len(left\_part)=len(right\_part)$ ，但由于C++向下取整的特性，两边长度的条件并不会成立，实际上某一部分会比另一个部分多出一个元素。多出的那个元素，就是我们要找的中位数。

C++的特性，实际上是缩小了 $j$ 的取值， $i$ 的取值也会在循环中间接缩小一点，所以中位数一定是在right_part里面！

即: $median = min(A[i], B[j])$
当 $m+n$ 为偶数，就很容易了， $median = (max(left\_part) + min(right\_part)) *0.5$

至此，我们需要讨论的点已经全部清楚了，怎么样，这就是LeetCode的“魅力”！

代码：

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int m = nums1.size();
        const int n = nums2.size();
        if(m > n) return findMedianSortedArrays(nums2, nums1);//我们是假设n>=m的
        const int k = (m + n) / 2;
        int imin = 0;
        int imax = m;
        while(imin <= imax){
            int i = (imin + imax) / 2;
            int j = (k-i);
            if (i < imax && nums2[j-1] > nums1[i]){
                imin = i + 1; // i 太小了
            }
            else if (i > imin && nums1[i-1] > nums2[j]) {
                imax = i - 1; // i 太大了
            }
            else{
                //此时i刚刚好
                //我们用INT_MIN, INT_MAX(相当于无穷小和无穷大)来代替不存在的情况
                int maxLeft = max(i <= 0 ? INT_MIN : nums1[i-1],
                    j <= 0 ? INT_MIN : nums2[j-1]);
                if((m + n) % 2 == 1)
                    return maxLeft;
                
                int minRight = min(i >= m ? INT_MAX: nums1[i],
                    j >= n ? INT_MAX : nums2[j]);
                return (maxLeft + minRight) * 0.5;
            }
        }
        return 0.0;
    }
};

复杂度分析

时间复杂度： $O(log(min(m, n)))$ ，因为查找的空间每次都会缩短为原来的一半，且这个空间的初始长度取决于m, n的最小值
空间复杂度： $O(1)$ 我们只使用了一些局部变量，没有引入新的内存来存放数组

LeetCode实战004 寻找两个有序数组的中位数

题目描述

题目解析

解法：二分查找法

复杂度分析

猜你喜欢

热点阅读