题目描述
这是 LeetCode 上的 4. 寻找两个正序数组的中位数 ，难度为 困难。
Tag : 「二分」、「分治」
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出并返回这两个正序数组的「中位数」。
示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2 复制代码
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5 复制代码
示例 3：
输入：nums1 = [0,0], nums2 = [0,0] 输出：0.00000 复制代码
示例 4：
输入：nums1 = [], nums2 = [1] 输出：1.00000 复制代码
示例 5：
输入：nums1 = [2], nums2 = [] 输出：2.00000 复制代码
提示：
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10610^6106 <= nums1[i], nums2[i] <= 10610^6106
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
朴素解法
如果忽略进阶的 O(log(m+n))O(\log{(m + n)})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)O(m+n)，对合并数组进行排序的复杂度是 O((m+n)log(m+n))O((m + n)\log{(m + n)})O((m+n)log(m+n))。整体复杂度是 O((m+n)log(m+n))O((m + n)\log{(m + n)})O((m+n)log(m+n))
- 空间复杂度：O(1)O(1)O(1)
注意：Arrays.sort() 不只有双轴快排实现，这里的复杂度分析是假定其使用双轴快排。
分治解法
首先可以将原问题等效为：从两个有序数组中找第 k 小的数。
分两种情况讨论：
- 总个数为偶数：找到
第 (total / 2) 个小的数和第 (total / 2 + 1) 个小的数，结果为两者的平均值。 - 总个数为奇数：结果为
第 (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(\log{(m + n)})O(log(m+n))
- 空间复杂度：O(1)O(1)O(1)
总结
今天这道题，我给你介绍了两种技巧：
- 在机试或者竞赛中，目的是尽可能快的 AC，所以 Java 可以直接不写
private的修饰符（不写代表使用默认的包权限），这没有问题，不用纠结 - 在机试或者竞赛中，遇到一些是从文字上限制我们的题目，例如本题限制我们使用 O(log(m+n))O(\log{(m+n)})O(log(m+n)) 算法。可以分析是否能够不按照限制要求来做，具体分析思路为：
- 先有一个很容易实现的算法思路。例如本题很容易就想到直接使用双指针找第 k 个小的数，复杂度为 O(n)O(n)O(n)。
- 看题目的数据规模 ① 是否支撑我们使用限制以外的算法。例如本题数据规模只有 1000 + 1000 = 2000。
- 根据数据规模，判断我们的朴素算法计算机是否可以在 1s 内处理完 ② ，即判断运算次数是否在 10710^7107 以内 ③ 。例如本题使用双指针算法，指针移动和判断大小算一次运行，由于数据只有 2000，距离 10710^7107 还很远，所以完
- 全足够了
说明 ①：正规的算法题目都会提供数据规模，LeetCode 上一些旧题目没有提供，是因为当时出的时候不太规范，LeetCode 新题、其他 OJ 平台题目，算法竞赛题目都会有。
说明 ②：即使是最严格的 OJ 中最简单的题目，也会提供 1s 的运行时间，超过这个时间才算超时。
说明 ③：计算器 1s 内极限的处理速度是 10810^8108 ，但为了尽可能不出现错误提交，使用技巧时尽量和 10710^7107 进行比较。
注意：这两个技巧，我只推荐在机试或者竞赛（尽可能快 AC 的场景）中使用。平时练习或者和面试的时候必须老实按照题目要求来。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.4 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
