美文网首页
LeetCode实战004 寻找两个有序数组的中位数

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

作者: Rooooyy | 来源:发表于2019-05-10 11:10 被阅读0次

    原题链接

    题目描述

    给定两个大小为 m 和 n 的有序数组 nums1nums2

    请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

    你可以假设 nums1nums2 不会同时为空。

    示例 1:

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

    示例 2:

    nums1 = [1, 2]
    nums2 = [3, 4]
    
    则中位数是 (2 + 3)/2 = 2.5
    

    题目解析

    解决这个问题,我们必须要搞清楚两个问题:

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

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

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

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

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

    解法:二分查找法

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

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

    首先,让我们在任一位置 iA 划分成两个部分(注意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]

    同样我们在位置 jB 进行划分:

              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]
    

    如果ij的取值足够合适,使得:

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

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

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

    上面的两个条件,等价于:

    1. i+j=m-i+n-j \Rightarrow j=\frac{m+n}2
    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

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


    接下来,我们来具体设计我们的二分算法:

    1. imin=0, imax=m,它们夹成了一个 i 的初始搜索区间

    2. 在二分查找法中,被查找的 i 应该赋予这个区间的中值,即i=\frac{imin+imax}2, 那么 j 也可以根据j = \frac{m+n+1}2求得一个值

    3. 现在我们来检查上面的条件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

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

    这里我们要证明一下 ij 的取值关系

    由于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 寻找两个有序数组的中位数

          本文链接:https://www.haomeiwen.com/subject/gubooqtx.html