【Leetcode】4.Median of Two Sorted Arrays

题目:给两个已排序的数组,长度分别为 m 和 n,找出两个数组的中位数。要求时间复杂度为 O(log(m+n))。
例如:
nums1 = [1, 3]; nums2 = [2]; 则中位数为 2
nums1 = [1,2]; nums2 = [3, 4]; 则中位数为 (2+3)/2 = 2.5

这个题目不难,问题在于他要求了算法的时间复杂度,也就是说第一反应的遍历合成新数组然后找出中位数这个最简单的方法不行,因为其时间复杂度太高。

第二个思路是参考网站讨论区这个答案,帖子很详细,记录如下。


首先,思考中位数的含义:统计学中,中位数的作用是将数集分割成两等份,其中一个数集永远比另一个大。

如果,随机将数组 A 切割,A 有 m 个数字,那么有 m+1 种切割方式。分为左右两个部分 length(left_A) = i, length(right_A) = m-i,左右可能为空。同样,将数组 B 用 j 切割,将 left_A 和 left_B 组成 left_part,同理获得 right_part。则:

length(left_part) == length(right_part)
max(left_part) <= min(right_part)
则:median = ( max(left_part) + min(right_part) )/2

那么要保证以上两个条件,则需要:

i + j == m-i + n - j (or: m-i + n-j + 1)  // 若 n >= m, 可设置 i = 0~m, j = (m + n + 1)/2 - i
B[j-1] <= A[i] and A[i-1] <= B[j]

ps.1 先假定 A[i-1], B[j-1], A[i], B[j] 总存在,之后再考虑边缘值问题
ps.2 设定 n>=m,是为了保证 在如此设定 i,j 值的情况下 j 是个非负数

因此,我们需要做的是:

在 [0, m] 区间内找到 i,满足:B[j-1] <= A[i] 和 A[i-1] <= B[j] ( j=(m+n+1)/2 -i )

然后做一个二叉树查找:

  1. 设置 imin = 0, imax = m, 然后在 [imin, imax] 中开始查找
  2. 设置 i = (imin + imax)/2, j = (m + n + 1)/2 - i
  3. 有三种情况我们要考虑:
    a. B[j-1] <= A[i] and A[i-1] <= B[j]:意味着找到了 i,停止查找
    b. B[j-1] > A[i]:意味着 i 太小,调整搜索范围至 [i+1, imax]
    c. A[i-1] > B[j]:意味着 i 太大,调整搜索方位至 [imin, i-1]

找到 i,则中位数也可以确定了:
m+n 为奇数,则中位数为 max(A[i-1], B[j-1])
m+n 为偶数,则中位数为 (max(A[i-1], B[j-1]) + min(A[i], B[j]))/2

现在考虑边缘值问题:当 i,j 值为 0 或者 m、n 时,A[i-1], B[j-1], A[i], B[j] 可能不存在。实际上,这种情况更简单,只需要在一边寻找即可。比如,当 A[i-1] 不存在,那么我们不需要满足 A[i-1] <= B[j]。


以上为分析过程,我的 C++ 代码如下:

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    if(m > n) return findMedianSortedArrays(nums2,nums1);

    int i,j, max_left, min_right;
    int imin = 0, imax = m;
    
    while(imin <= imax){
        i = (imin + imax)/2;
        j = (m + n + 1)/2 - i;
        if(i < m && nums2[j-1] > nums1[i]) imin = i+1;
        else if( i > 0 && nums1[i-1] > nums2[j]) imax = i-1;
        else{
            if(i==0) max_left = nums2[j-1];
            else if(j==0) max_left = nums1[i-1];
            else max_left = max(nums1[i-1], nums2[j-1]);
            break;
        }
    }
    
    if((m+n) %2 == 1) return max_left;

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

推荐阅读更多精彩内容