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

原题链接

题目描述

给定两个大小为 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)我们只使用了一些局部变量,没有引入新的内存来存放数组
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,590评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 86,808评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,151评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,779评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,773评论 5 367
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,656评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,022评论 3 398
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,678评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 41,038评论 1 299
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,756评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,411评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,005评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,973评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,053评论 2 350
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,495评论 2 343