H5W3
当前位置:H5W3 > java > 正文

【Java】【每日算法/刷穿 LeetCode】4. 寻找两个正序数组的中位数(困难)

【每日算法/刷穿 LeetCode】4. 寻找两个正序数组的中位数(困难)

宫水三叶发布于 今天 11:51

题目描述

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

进阶:你能设计一个时间复杂度为 $O(log (m+n))$ 的算法解决此问题吗?

示例 1:

解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3:

示例 4:

示例 5:

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

朴素解法

如果忽略进阶的 $O(log(m + n))$ 要求,这道题就非常简单。

一个比较直观的做法:将两个数组合并,排序,然后分别取得 total / 2(total - 1) / 2 两个位置的数,取两者平均值。

这样做的目的是为了避免分情况讨论:合并后的数组长度是奇数还是偶数。

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
int[] arr = new int[n + m];
int idx = 0;
for (int i : nums1) arr[idx++] = i;
for (int i : nums2) arr[idx++] = i;
Arrays.sort(arr);
int l = arr[(n + m) / 2], r = arr[(n + m - 1) / 2];
return (l + r) / 2.0;
}
}

时间复杂度:合并两个数组的复杂度是 $O(m + n)$,对合并数组进行排序的复杂度是 $O((m + n)log(m + n))$。整体复杂度是 $O((m + n)log(m + n))$

空间复杂度:$O(1)$

注意:Arrays.sort() 不只有双轴快排实现,这里的复杂度分析是假定其使用双轴快排。


分治解法

首先可以将原问题等效为:从两个有序数组中找第 k 小的数。

分两种情况讨论:

  1. 总个数为偶数:找到 第 (total / 2) 个小的数第 (total / 2 + 1) 个小的数,结果为两者的平均值。
  2. 总个数为奇数:结果为 第 (total / 2 + 1) 个小的数

具体思路为:

  • 默认第一个数组比第二个数组的有效长度短,如果不满足,则调换两个数组(这也是一个常用技巧,目的是减少边界处理工作:原本需要对两个数组做越界检查,现在只需要对短的数组做越界检查)
  • 第一个数组的有效长度从 i 开始,第二个数组的有效长度从 j 开始,其中 [i,si - 1] 是第一个数组的前 k / 2 个元素,[j,sj - 1] 是第二个数组的前 k - k / 2 个元素(为了确保 k 为奇数的时候正确)
  • nums1[si - 1] > nums2[sj - 1]:则表示第 k 小一定不在 [j,sj - 1] 中,即在 [i,n][sj,m]
  • nums1[si - 1] <= nums2[sj - 1]:则表示第 k 小一定不在 [i,si - 1] 中,即在 [si,n][j,m]
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int tot = nums1.length + nums2.length;
if (tot % 2 == 0) {
int left = find(nums1, 0, nums2, 0, tot / 2);
int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
return (left + right) / 2.0;
} else {
return find(nums1, 0, nums2, 0, tot / 2 + 1);
}
}
int find(int[] n1, int i, int[] n2, int j, int k) {
if (n1.length - i > n2.length - j) return find(n2, j, n1, i, k);
if (i >= n1.length) return n2[j + k - 1];
if (k == 1) {
return Math.min(n1[i], n2[j]);
} else {
int si = Math.min(i + (k / 2), n1.length), sj = j + k - (k / 2);
if (n1[si - 1] > n2[sj - 1]) {
return find(n1, i, n2, sj, k - (sj - j));
} else {
return find(n1, si, n2, j, k - (si - i));
}
}
}
}

时间复杂度:每次递归 k 的规模都减少一半,复杂度为 $O(log(m + n))$

空间复杂度:$O(1)$


总结

今天这道题,我给你介绍了两种技巧:

  1. 在机试或者周赛中,目的是尽可能快的 AC,所以 Java 可以直接不写 private 的修饰符(不写代表使用默认的包权限),这没有问题,不用纠结
  2. 在机试或者周赛中,遇到一些是从文字上限制我们的题目,例如本题限制我们使用 O(log (m+n)) 算法。可以分析是否能够不按照限制要求来做,具体分析思路为:

    2.1 先有一个很容易实现的算法思路。例如本题很容易就想到直接使用双指针找第 k 个小的数,复杂度为 O(n)。

    2.2 看题目的数据规模①是否支撑我们使用限制以外的算法。例如本题数据规模只有 1000 + 1000 = 2000。

    2.3 根据数据规模,判断我们的朴素算法计算机是否可以在 1s 内处理完②,即判断运算次数是否在 10^7 以内③。例如本题使用双指针算法,指针移动和判断大小算一次运行,由于数据只有 2000,距离 10^7 还很远,所以完全足够了

说明 ①:正规的算法题目都会提供数据规模,LeetCode 上一些旧题目没有提供,是因为当时出的时候不太规范,LeetCode 新题、其他 OJ 平台题目,算法竞赛题目都会有。

说明 ②:即使是最严格的 OJ 中最简单的题目,也会提供 1s 的运行时间,超过这个时间才算超时。

说明 ③:计算器 1s 内极限的处理速度是 10^8 ,但为了尽可能不出现错误提交,使用技巧时尽量和 10^7 进行比较。

注意:这两个技巧,我只推荐在机试或者周赛(尽可能快 AC 的场景)中使用。平时练习或者和面试的时候必须老实按照题目要求来。


最后

这是我们「刷穿 LeetCode」系列文章的第 No.4 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 4/1916

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:Github 地址 & Gitee 地址。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。

算法与数据结构
LeetCode题解
算法面试
java算法数据结构leetcode数据结构与算法
阅读 32发布于 今天 11:51
本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议

刷穿LeetCode
公众号:「宫水三叶的刷题日记 」。每天十分钟,快乐学算法 ~
avatar

宫水三叶

关注公众号:「宫水三叶的刷题日记 」。

1 声望
0 粉丝

0 条评论
得票时间

avatar

宫水三叶

关注公众号:「宫水三叶的刷题日记 」。

1 声望
0 粉丝

宣传栏

题目描述

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

进阶:你能设计一个时间复杂度为 $O(log (m+n))$ 的算法解决此问题吗?

示例 1:

解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3:

示例 4:

示例 5:

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

朴素解法

如果忽略进阶的 $O(log(m + n))$ 要求,这道题就非常简单。

一个比较直观的做法:将两个数组合并,排序,然后分别取得 total / 2(total - 1) / 2 两个位置的数,取两者平均值。

这样做的目的是为了避免分情况讨论:合并后的数组长度是奇数还是偶数。

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
int[] arr = new int[n + m];
int idx = 0;
for (int i : nums1) arr[idx++] = i;
for (int i : nums2) arr[idx++] = i;
Arrays.sort(arr);
int l = arr[(n + m) / 2], r = arr[(n + m - 1) / 2];
return (l + r) / 2.0;
}
}

时间复杂度:合并两个数组的复杂度是 $O(m + n)$,对合并数组进行排序的复杂度是 $O((m + n)log(m + n))$。整体复杂度是 $O((m + n)log(m + n))$

空间复杂度:$O(1)$

注意:Arrays.sort() 不只有双轴快排实现,这里的复杂度分析是假定其使用双轴快排。


分治解法

首先可以将原问题等效为:从两个有序数组中找第 k 小的数。

分两种情况讨论:

  1. 总个数为偶数:找到 第 (total / 2) 个小的数第 (total / 2 + 1) 个小的数,结果为两者的平均值。
  2. 总个数为奇数:结果为 第 (total / 2 + 1) 个小的数

具体思路为:

  • 默认第一个数组比第二个数组的有效长度短,如果不满足,则调换两个数组(这也是一个常用技巧,目的是减少边界处理工作:原本需要对两个数组做越界检查,现在只需要对短的数组做越界检查)
  • 第一个数组的有效长度从 i 开始,第二个数组的有效长度从 j 开始,其中 [i,si - 1] 是第一个数组的前 k / 2 个元素,[j,sj - 1] 是第二个数组的前 k - k / 2 个元素(为了确保 k 为奇数的时候正确)
  • nums1[si - 1] > nums2[sj - 1]:则表示第 k 小一定不在 [j,sj - 1] 中,即在 [i,n][sj,m]
  • nums1[si - 1] <= nums2[sj - 1]:则表示第 k 小一定不在 [i,si - 1] 中,即在 [si,n][j,m]
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int tot = nums1.length + nums2.length;
if (tot % 2 == 0) {
int left = find(nums1, 0, nums2, 0, tot / 2);
int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
return (left + right) / 2.0;
} else {
return find(nums1, 0, nums2, 0, tot / 2 + 1);
}
}
int find(int[] n1, int i, int[] n2, int j, int k) {
if (n1.length - i > n2.length - j) return find(n2, j, n1, i, k);
if (i >= n1.length) return n2[j + k - 1];
if (k == 1) {
return Math.min(n1[i], n2[j]);
} else {
int si = Math.min(i + (k / 2), n1.length), sj = j + k - (k / 2);
if (n1[si - 1] > n2[sj - 1]) {
return find(n1, i, n2, sj, k - (sj - j));
} else {
return find(n1, si, n2, j, k - (si - i));
}
}
}
}

时间复杂度:每次递归 k 的规模都减少一半,复杂度为 $O(log(m + n))$

空间复杂度:$O(1)$


总结

今天这道题,我给你介绍了两种技巧:

  1. 在机试或者周赛中,目的是尽可能快的 AC,所以 Java 可以直接不写 private 的修饰符(不写代表使用默认的包权限),这没有问题,不用纠结
  2. 在机试或者周赛中,遇到一些是从文字上限制我们的题目,例如本题限制我们使用 O(log (m+n)) 算法。可以分析是否能够不按照限制要求来做,具体分析思路为:

    2.1 先有一个很容易实现的算法思路。例如本题很容易就想到直接使用双指针找第 k 个小的数,复杂度为 O(n)。

    2.2 看题目的数据规模①是否支撑我们使用限制以外的算法。例如本题数据规模只有 1000 + 1000 = 2000。

    2.3 根据数据规模,判断我们的朴素算法计算机是否可以在 1s 内处理完②,即判断运算次数是否在 10^7 以内③。例如本题使用双指针算法,指针移动和判断大小算一次运行,由于数据只有 2000,距离 10^7 还很远,所以完全足够了

说明 ①:正规的算法题目都会提供数据规模,LeetCode 上一些旧题目没有提供,是因为当时出的时候不太规范,LeetCode 新题、其他 OJ 平台题目,算法竞赛题目都会有。

说明 ②:即使是最严格的 OJ 中最简单的题目,也会提供 1s 的运行时间,超过这个时间才算超时。

说明 ③:计算器 1s 内极限的处理速度是 10^8 ,但为了尽可能不出现错误提交,使用技巧时尽量和 10^7 进行比较。

注意:这两个技巧,我只推荐在机试或者周赛(尽可能快 AC 的场景)中使用。平时练习或者和面试的时候必须老实按照题目要求来。


最后

这是我们「刷穿 LeetCode」系列文章的第 No.4 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 4/1916

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:Github 地址 & Gitee 地址。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。

算法与数据结构
LeetCode题解
算法面试

本文地址:H5W3 » 【Java】【每日算法/刷穿 LeetCode】4. 寻找两个正序数组的中位数(困难)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址