首页
首页 教程 派聪明
  • 首页
  • 教程
  • 派聪明
  • 登录
登录技术派畅享更多权益

用户名密码登录

其他登录:
icon_GitHubCreated with sketchtool.
绑定星球,畅享VIP服务

微信扫码/长按识别登录

输入验证码
有效期五分钟 👉 手动刷新

登录即同意 用户协议 和 隐私政策

绑定二哥编程星球,畅享 VIP 尊享服务!

戳我了解如何获取星球编号,新窗口打开

添加二哥微信 itwanger 审核更快

记得备注 星球编号
我会根据星球编号进行审核
1
两数之和
更新时间: 2023年12月09日
星球
2
两数相加
更新时间: 2023年12月10日
星球
3
无重复字符的最长子串
更新时间: 2023年12月12日
星球
4
寻找两个正序数组的中位数
更新时间: 2023年12月14日
星球
5
最长回文子串
更新时间: 2023年12月18日
星球
6
Z 字行变换
更新时间: 2023年12月26日
星球
7
整数反转
更新时间: 2023年12月28日
星球
8
字符串转成整数
更新时间: 2024年01月01日
星球
9
回文数
更新时间: 2024年01月03日
星球
10
正则式匹配
更新时间: 2024年01月17日
星球
11
盛最多水的容器
更新时间: 2024年01月20日
星球
12
整数转罗马数字
更新时间: 2024年01月21日
星球
13
罗马数字转整数
更新时间: 2024年01月22日
星球
14
最长公共前缀
更新时间: 2024年01月23日
星球
15
三数之和
更新时间: 2024年01月25日
星球
16
最接近的三数之和
更新时间: 2024年01月27日
星球
17
电话号码的字母组合
更新时间: 2024年01月29日
星球
18
四数之和
更新时间: 2024年01月30日
星球
19
删除链表中的倒数第N个节点
更新时间: 2024年01月31日
星球
20
有效的括号
更新时间: 2024年02月01日
星球
21
合并两个有序链表
更新时间: 2024年02月02日
星球
22
括号生成
更新时间: 2024年02月03日
星球
23
合并K个升序链表
更新时间: 2024年02月04日
星球
24
两两交换链表中的节点
更新时间: 2024年02月06日
星球
25
K个一组翻转链表
更新时间: 2024年02月07日
星球
26
删除有序数组中的重复项
更新时间: 2024年02月11日
星球
27
移除元素
更新时间: 2024年02月14日
星球
28
实现 strStr()
更新时间: 2024年02月19日
星球
29
两数相除
更新时间: 2024年02月22日
星球
30
串联所有单词的子串
更新时间: 2024年02月27日
星球
31
下一个排列
更新时间: 2024年02月29日
星球
32
最长有效括号
更新时间: 2024年05月30日
星球
33
搜索旋转排序数组
更新时间: 2024年06月03日
星球
34
在排序数组中查找元素的头尾位置
更新时间: 2024年06月14日
星球
35
搜索插入位置
更新时间: 2024年06月15日
星球
36
有效的数独
更新时间: 2024年06月16日
星球
37
解数独
更新时间: 2024年08月01日
星球
38
外观数列
更新时间: 2024年08月02日
星球
39
组合总和
更新时间: 2024年08月03日
星球
40
组合总和②
更新时间: 2024年08月04日
星球
41
缺失的第一个整数
更新时间: 2024年08月06日
星球
42
接雨水
更新时间: 2024年08月07日
星球
43
字符串相乘
更新时间: 2024年08月08日
星球
44
通配符匹配
更新时间: 2024年09月04日
星球
45
跳跃游戏
更新时间: 2024年09月06日
星球
46
全排列
更新时间: 2024年09月08日
星球
47
全排列②
更新时间: 2024年09月14日
星球
48
旋转图像
更新时间: 2024年09月18日
星球
49
字母异位词分组
更新时间: 2024年09月20日
星球
50
Pow(x, n)
更新时间: 2024年09月29日
星球
51
N 皇后
更新时间: 2024年11月14日
星球
52
N 皇后②
更新时间: 2024年11月14日
星球
53
最大子数组和
更新时间: 2024年11月16日
星球
54
螺旋矩阵
更新时间: 2024年11月20日
星球
55
跳跃游戏
更新时间: 2024年11月21日
星球
56
合并区间
更新时间: 2025年01月26日
星球
57
插入区间
更新时间: 2025年02月01日
星球
关注公众号
原创
二哥的 LeetCode 刷题笔记:004.寻找两个正序数组的中位数

我每天都在读《二哥的 LeetCode 刷题笔记》。 ------------------------by鲁迅

题意

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

你给出的算法的时间复杂度应该为 O(log (m+n)) 。

示例

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

难度

困难

好吧,第四道就遇到了 hard,算法新手很容易到这就被劝退了,但其实这道题并没有想象中那么可怕,请深吸一口气,告诉自己一定能行,笔试的时候其实也需要这样的心态。

尤其是在那种紧张氛围中,更需要保持冷静,不要被题目吓到,一定要相信自己,相信自己的能力,相信自己的实力。

实在做不出来,如果是比较热心肠的面试官,甚至会给你一些提示的,所以不要打退堂鼓,劳资打的就是精锐(😁)。

分析 1

首先,对于算法新手来说,这道题需要搞清楚几个概念:

  • 正序的数组长什么样子?
  • 两个数组如何合并?
  • 中位数是什么?

正序的数组,也就是从小到大排序过的数组,就是数组中的元素从左到右,依次变大的数组,如下:

[1,2,3,4,5,6,7,8,9,10]

当然也可以跳着来,但一定是后面的数比前面的数大,如下:

[1,5,13,17,18,19]

两个数组如何合并呢?

最简单的就是使用 for 循环进行遍历,把两个数组复制到一个新的数组当中,这个我在《二哥的 Java 进阶之路》中讲数组的时候讲过。

int[] array1 = {1, 2, 3};
int[] array2 = {4, 5, 6};

// 创建一个新数组,长度为两个数组长度之和
int[] mergedArray = new int[array1.length + array2.length];

// 复制第一个数组到新数组
int index = 0;
for (int element : array1) {
    mergedArray[index++] = element;
}

// 复制第二个数组到新数组
for (int element : array2) {
    mergedArray[index++] = element;
}

那高级一点的话,可以使用 Arrays.copyOfRange() 复制,它底层用到的是 System.arraycopy(),这个方法是 native 方法,效率更高(数组那一节里也讲过,球友可以过去看一眼,很快就能明白)。

那什么是中位数呢?

中位数,就是把一组数据按照从小到大的顺序排列,位于中间位置的那个数,如果数据的个数是奇数,那么中位数就是最中间的那个数,如果数据的个数是偶数,那么中位数就是最中间两个数的平均值。

  • 奇数个数值:例如,在数据集 [1, 3, 3, 6, 7, 8, 9] 中,中位数是 6。
  • 偶数个数值:例如,在数据集 [1, 2, 3, 4, 5, 6, 8, 9] 中,中间的两个数是 4 和 5,所以中位数是 (4 + 5) / 2 = 4.5。

中位数与平均值(或算术平均数)不同。平均值是所有数值的总和除以数值的个数,而中位数是数据集的中间值。

好,明白了这三个概念,问题就变得简单了,对吧?

来吧,先用 System.arraycopy 合并两个数组,然后再用 Arrays.sort() 排序,最后再根据数组的长度是奇数还是偶数,来计算中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 创建一个新数组,长度为两个数组长度之和
        int[] temp = new int[nums1.length + nums2.length];

        // 复制第一个数组到新数组
        System.arraycopy(nums1, 0, temp, 0, nums1.length);

        // 复制第二个数组到新数组
        for (int i = 0; i < nums2.length; i++)
            temp[i + nums1.length] = nums2[i];
        // 这里其实还可以继续用 System.arraycopy(),但是为了方便大家理解,我就 for 循环也用一下

        // 对合并后的数组进行排序
        Arrays.sort(temp);

        // 计算中位数
        int num1 = temp[temp.length / 2];
        // 如果数组长度是奇数
        if ((temp.length & 1) == 1)
            return num1 * 1.0; // 直接返回中间的元素
        else
            // 如果数组长度是偶数,返回中间两个元素的平均值
            return (num1 + temp[temp.length / 2 - 1]) / 2.0;
    }
}

其中 (temp.length & 1) == 1 用到了位运算,不懂的球友可以戳链接了解一下。

在二进制中,奇数的最低位总是 1,而偶数的最低位总是 0。因此,将 temp.length 与 1 进行按位与操作实际上是在检查 temp.length 的最低位是 1 还是 0。如果结果是 1,那么 temp.length 是奇数;如果结果是 0,则是偶数。

更直观的方式是用取模运算符 %,我在讲 HashMap 的时候有讲过,可以戳链接去了解。

int[] array = {1, 2, 3, 4, 5};

// 使用模运算符 % 检查数组长度是否是奇数
if (array.length % 2 == 1) {
    // 如果是奇数
    System.out.println("数组长度是奇数。");
} else {
    // 如果是偶数
    System.out.println("数组长度是偶数。");
}

模运算符 % 返回两个数相除的余数。如果数组长度除以 2 的余数为 1,则表示数组长度是奇数;如果余数为 0,则表示数组长度是偶数。

我的方法 findMedianSortedArrays 返回的是 double 类型,所以我们在求出中位数的时候在题解中使用 * 1.0 或 / 2.0 来确保结果是浮点数(double 类型),而不是整数。这在计算平均值或需要精确的小数结果时尤为重要,避免了整数除法的小数截断问题,大家可以试一下不乘以 1.0 或不除以 2.0 的结果。

好,我们来看一下题解效率。

虽然也通过了,但时间复杂度:$O((n+m) \log(n+m))$,合并数组:O(m + n),其中 m 和 n 分别是两个数组的长度,排序数组:O((m + n) log (m + n)),并没有达到题目的要求。

分析 2

不知道球友们之前有没有学过 归并排序,如果没有的话,可以戳链接观看视频学习一下(下图来源于该视频教程,作者请叫我 AXin)。

这里总结一下,什么是归并排序?

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。

归并排序的核心思想是分治法,先递归分解数组,再合并数组。将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

例如,对数组 [3, 1, 4, 1, 5, 9, 2, 6] 进行归并排序:

  • 分解为 [3, 1, 4, 1] 和 [5, 9, 2, 6]。
  • 继续分解,比如 [3, 1, 4, 1] 分解为 [3, 1] 和 [4, 1]。
  • 继续分解,直到子数组只包含一个元素。
  • 开始合并,例如将 [3, 1] 合并为 [1, 3]。
  • 继续合并其他子数组。
  • 最后,将所有合并的子数组合并为最终的排序数组。

它每一层的拆分都是对半的,所以时间复杂度是$O(\log{n})$,而每一层的合并都是对两个数组的合并,所以时间复杂度是$O(n)$,所以整体的时间复杂度是$O(n\log{n})$。

分解步骤涉及将数组递归地分成两半,直到每个子数组只包含一个元素。对于长度为 n 的数组,这个分解过程的时间复杂度是 O(log n)。

为什么是 O(log n)?因为每次递归调用都将数组分为两部分,所以深度为 log n(这里的对数是以 2 为底)。例如,一个长度为 8 的数组分解成长度为 1 的子数组需要 3 步(8 -> 4 -> 2 -> 1),因为 2^3 = 8。

归并步骤涉及将两个已排序的子数组合并成一个已排序的数组。每次合并操作的时间复杂度是 O(n),因为它涉及遍历两个子数组的所有元素。例如,合并长度为 4 的子数组需要 4 步(1 + 1 + 1 + 1)。

根据归并思想,我们可以写出下面这样的题解。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        // 判断总元素数量是奇数还是偶数
        boolean flag = ((m + n) % 2) == 0;
        int p

已加入二哥编程星球,即刻绑定星球编号解锁🔐

该文档仅「二哥编程星球」的VIP用户可见

二哥的编程星球内容包括:

1. 付费文档: 技术派、MYDB 等项目配套的 120+篇教程查看权限

2. 面试指南: 校招、社招的 40 万+字面试求职攻略

3. 智能助手: 无限期使用派聪明 AI 助手,已对接讯飞星火和 ChatGPT双通道,不用花 1 分钱

4. 专属问答: 向二哥 1v1 发起提问,内容不限于 offer 选择、学习路线、职业规划等

5. 简历修改: 提供简历修改服务,附赠星球 100+优质简历模板可供参考

6. 学习环境: 打造一个沉浸式的学习环境,有一种高考冲刺、大学考研的氛围


二哥的星球

》步骤①:微信扫描上方二维码,点击「加入知识星球」按钮

》步骤②:访问星球置顶帖球友必看: https://t.zsxq.com/11rEo9Pdu,获取项目配套文档的语雀访问地址和密码

已加入星球,绑定星球编号
删除提醒

确定删除《二哥的 LeetCode 刷题笔记:004.寻找两个正序数组的中位数》吗

2人已点赞

回复