LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

我一直会卡在这道题上,在网上看了半个小时的博客,愣是没看懂。后来看到 YouTube 上有一个印度大哥的讲解,豁然开朗。

印度大哥的视频地址:Binary Search : Median of two sorted arrays of different sizes.

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0 Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题目分析

其实这道题我卡就卡在,一直没有想清楚应该如何划分两个数组。直接看LeetCode论坛上的答案,也一直没有搞懂。本题只是想求中位数,并不用管其他的数字。

那么核心就在于,如何划分两个数组,使得两个数组组合起来后,成为一个在中位数附近相对有序的数组即可。

具体实例分析

算法分析

定义两个变量 partitionX、 partitionY,分别分割X数组和Y数组,记为X1, X2, Y1, Y2。使得

len(X1) + len(Y1) == len(X2) + len(Y2)
或
len(X1) + len(Y1) == len(X2) + len(Y2) + 1

并且使得 max(X1) < min(Y2), max(Y1) < min(X2),这样数组就被完整地分成了两部分。

如果两个数组长度的和是奇数,那么必然是 max(X1, Y1)了; 如果两个数组长度的和是偶数,那么是 (max(X1, Y1) + min(X2, Y2)) / 2。

代码实现

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int x = nums1.length, y = nums2.length;
    int low = 0, high = x;

    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;

        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];

        int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
        int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 == 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (minRightX < maxLeftY) {
            low = partitionX + 1;
        } else {
            high = partitionX - 1;
        }
    }

    throw new RuntimeException();
}

总结

这道题如果能把图画出来,理解起来就很容易。但是这道题在LeetCode中的难度是hard,因为编写代码并不容易,有很多边界条件:

  1. 数组长度的奇偶
  2. 移动过程中,某个数组被切割后可能为空

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

Python内置函数int高级用法

int()函数常用来把其他类型转换为整数,例如: >>>int(3.2) 3 >>>int(1/3) 其实,int是Python内置类型之一,之所以能够当作函数...

2609
来自专栏小詹同学

Leetcode打卡 | No.015 三数之和

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1272
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦了...

3655
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2612
来自专栏前端儿

A+B Problem(V)

做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

831
来自专栏数据结构与算法

1200 同余方程

1200 同余方程 2012年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2834
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

1832
来自专栏Python小屋

Python内置函数int()高级用法

int()函数常用来把其他类型转换为整数,例如: >>> int(3.2) 3 >>> int(1/3) 0 其实,int是Python内置类型之一,之所以能...

3067
来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

3225
来自专栏数据小魔方

让执着成为一种习惯——仿网易数独玫瑰气泡图

没有难学的技艺,只有不够辛勤的付出! 今天这篇文章推送仿的的是网易数独的一幅信息图,内容呈现的是全球各国人民对于养老所持的态度,数据来源于Pew Reserch...

4115

扫码关注云+社区

领取腾讯云代金券