4.寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数
题意
给定两个大小分别为 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 的结果。
好，我们来看一下题解效率。
004.%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E
6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0-
20231213162753.png
虽然也通过了，但时间复杂度：$ O((n+m) (n+m)) $，合并数组：O(m + n)，其中 m 和 n
分别是两个数组的长度，排序数组：O((m + n) log (m + n))，并没有达到题目的要求。
分析 2
不知道球友们之前有没有学过 归并排序，如果没有的话，可以戳链接观看视频学习一下
（下图来源于该视频教程，作者请叫我 AXin）
。
004.%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E
6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0-
20231213164207.png
这里总结一下，什么是归并排序？
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（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()
，而 每 一 层 的 合 并 都 是 对 两 个 数 组 的 合 并 ，所 以 时 间 复 杂 度 是
O(n) ， 所 以 整 体 的 时 间 复 杂 度 是 O(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 point1 = 0, point2 = 0; // 分别为 nums1 和 nums2 的指针
int remNum1 = 0, remNum2 = 0; // 用于存储当前遍历的元素和前一个元素
// 遍历两个数组的元素，直到到达中位数的位置
for (int i = 0; i <= (n + m) / 2; i++) {
remNum2 = remNum1; // 存储前一个元素
// 比较两个数组当前元素，取较小的那个
if (point1 < n && (point2 >= m || nums1[point1] < nums2[point2])) {
remNum1 = nums1[point1++];
} else {
remNum1 = nums2[point2++];
}
}
// 如果总元素数量是偶数，则中位数是中间两个数的平均值
if (flag) {
return (remNum1 + remNum2) / 2.0;
}
// 如果总元素数量是奇数，则中位数是中间的那个数
return remNum1 * 1.0;
}
}
当输入是 nums1 = [1,2] 和 nums2 = [3,4] 时，我们来模拟整个题解过程：
1. 初始化：
– nums1 的长度 n = 2，nums2 的长度 m = 2。
– 总长度 n + m = 4，所以总长度是偶数，flag = true。
– 设置两个数组的指针 point1 = 0，point2 = 0。
– 初始化 remNum1 和 remNum2 为 0，用来存储当前元素和前一个元素。
2. 开始遍历数组：
– 第一次循环（i = 0）：
• nums1[0] = 1，nums2[0] = 3。选择较小的 nums1[0]，remNum1 = 1，
point1 增加到 1。
– 第二次循环（i = 1）：
• nums1[1] = 2，nums2[0] = 3。选择较小的 nums1[1]，remNum2 =
remNum1 = 1，remNum1 = 2，point1 增加到 2。
– 第三次循环（i = 2）：
• nums1 已经遍历完，只剩 nums2。选择 nums2[0] = 3，remNum2 =
remNum1 = 2，remNum1 = 3，point2 增加到 1。
– 第四次循环（i = 3）：
• 同理，选择 nums2[1] = 4，remNum2 = remNum1 = 3，remNum1 =
4。
3. 计算中位数：
– 因为总长度是偶数（flag = true），中位数是最后两个遍历的数的平均值。
– remNum1 = 4，remNum2 = 3，所以中位数是 (4 + 3) / 2.0 = 3.5。
因此，对于 nums1 = [1,2] 和 nums2 = [3,4]，中位数是 3.5。
条件 point1 < n && (point2 >= m || nums1[point1] < nums2[point2]) 是用来确定在
合并两个排序数组的过程中，下一个要选取的元素是来自 nums1 还是 nums2。
1. **point1 < n**：
– 这是检查 nums1 的指针 point1 是否还在数组的范围内。如果 point1 已经等
于 n，意味着 nums1 中的所有元素都已经被考虑过了。
2. **point2 >= m**：
– 这是检查 nums2 的指针 point2 是否超出了数组的范围。如果 point2 大于或
等于 m，意味着 nums2 中的所有元素都已经被考虑过了。
3. **nums1[point1] < nums2[point2]**：
– 这是比较 nums1 和 nums2 当前指针位置的元素。如果 nums1 当前元素小于
nums2 当前元素，这个条件成立。
在合并两个排序数组时，我们希望按照排序顺序依次选取两个数组中的元素。这个条件帮
助我们决定接下来应该选取 nums1 还是 nums2 中的元素：
• 当 nums1 还有元素，并且 nums2 要么已经处理完，要么 nums1 的当前元素更小，
我们就选择 nums1 的当前元素。
• 如果条件不成立（即 nums1 处理完了，或者 nums1 的当前元素不小于 nums2 的当
前元素），我们就从 nums2 中选取元素。
这样的逻辑确保了合并后的数组是有序的，同时也高效地利用了两个已排序数组的性质。
004.%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E
6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0-
20231213171032.png
时间复杂度：$ O(n+m) $，归并到中位数：O(m + n)，每次从两个数组的开头取较小的
数，直到达到中位数的位置。
但题目要求的是 $ O((n+m)) $。
分析 3
根据中位数的定义，当数组长度为奇数时，中位数就是数组中的第(size + 1) / 2 个，偶
数的话，则是第(size + 1) / 2 个数和第(size + 1) / 2 + 1 个数的平均数。
来看这样子一组样例(从第一个开始计数)
nums1 : [2,5,8]
nums2 : [3,4,5,6,7,8,9,10]
合并后：[2,3,4,5,5,6,7,8,8,9,10]
nums1.length + nums2.length = 11，新数组的长度为奇数，所以中位数为(11 + 1) /
2，也就是新数组的第 6 个数（下标为 5）。
由于数组是排序过（升序）的，所以求中位数就变成了一个寻找第 K 小的数的问题了。
这里的“第 K 小”指的是如果所有元素都按升序排序，那么位于第 K 个位置的元素（从 1 开
始计数）。
例如，考虑数组 [3, 5, 2, 7, 4]，升序后是 [2, 3, 4, 5, 7]：
• 第 1 小的数是 2（最小的数）。
• 第 2 小的数是 3。
• 第 3 小的数是 4。
• 以此类推。
关于寻找第 K 小的数，我这里有一个视频，讲得很好，大家可以戳链接观
看：https://www.bilibili.com/video/BV1TR4y197X2
中位数本质上是数组排序后位于中间位置的数，因此它可以视为一个特殊的第 K 小的数
的问题。
• 当总元素个数是奇数时：中位数是第 (m + n + 1) / 2 小的数，其中 m 和 n 分别是两个
数组的长度。例如，如果两个数组总共有 11 个元素，那么中位数就是第 (11 + 1) / 2
= 6 小的数。
• 当总元素个数是偶数时：中位数是第 (m + n) / 2 和第 (m + n) / 2 + 1 小的数的平均
值。例如，如果两个数组总共有 10 个元素，那么中位数就是第 10 / 2 = 5 小的数和
第 6 小的数的平均值。
相信这个大家应该都明白了。
在这道题中，我们不需要合并两个数组来找到中位数。
相反，我们可以使用二分查找的方法找到第 K 小的数。这种方法在两个数组都是排序过
的情况下特别有效，因为我们可以使用二分查找法搜索第 K / 2 个元素（即两个数组中第
K 小的元素），并且由于两个数组中的元素有序，所以我们可以比较这两个第 K / 2 个元
素的值来决定如何继续搜索。
什么是二分查找法？
二分查找法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元
素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或
者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间
元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使
搜索范围缩小一半。
004.%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E
6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0-
20231214085109.png
比如说 A 数组「A1,A2,A3,A4,A5」，B 数组「B1,B2,B3,B4,B5」，一共有 10 个数，我们要
找出第 5 小的数和第 6 小的数，它们和的二分之一就是合并后数组的中位数，对吧？
那也就是我们要求两次，一次求第 5 小的数，一次求第 6 小的数。
求第 5 小的数时，我们可以先从 A 数组中 K/2 找，K = 5/2 = 2，也就是 A2；再从 B 数组
中找 K/2，K = 5/2 = 2，也就是 B2，然后比较 A2 和 B2。
如果 A2 < B2，那么 A1、A2 肯定不可能是第 5 小的数，因为最好的情况就是下面这样子，B2
都不是第 5 小，A1、A2 肯定不行，对吧？
004.%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E
6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0-
20231213225526.png
所以我们可以把 A1-1、A2-3 排除掉（假设-后跟的值，方便大家理解），于是两个数组变
成了这样子：
• A 数组「A1-5,A2-7,A3-8」
• B 数组「B1-2,B2-4,B3-6,B4-9,B5-10」
由于排除了两个数，所以 K = 5 - 2 = 3，变成了要找第 3 小的数，那么我们可以再从 A 数
组中找 K/2，K = 3/2 = 1，也就是 A1；再从 B 数组中找 K/2，K = 3/2 = 1，也就是 B1，然后
比较 A1 和 B1。
此时 B1-2 < A1-5，那么 B1 肯定不可能是第 3 小的数，因为最好的情况就是下面这样子，
A1 可能是第 3 小（还不确定 B2、B3 的值），但 B1 肯定不行，对吧？
004.%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E
6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0-
20231213232713.png
那把 B1 排除掉，于是两个数组变成了这样子：
• A 数组「A1-5,A2-7,A3-8」
• B 数组「B1-4,B2-6,B3-9,B4-10」
由于排除了一个数，所以 K = 3 - 1 = 2，变成了要找第 2 小的数，那么我们可以再从 A 数
组中找 K/2，K = 2/2 = 1，也就是 A1；再从 B 数组中找 K/2，K = 2/2 = 1，也就是 B1，然后
比较 A1 和 B1。
此时 B1-4 < A1-5，那么 B1 肯定不可能是第 2 小的数，
以此类推，直到 K = 1，也就是找到了第 1 小的数，也就是 5；再找第 6 小的数也是一样
的道理，最后求平均值就是中位数了。
我们来看题解：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int ans1 = getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1,
(nums1.length + nums2.length + 1) / 2);
int ans2 = getKth(nums1,0, nums1.length - 1, nums2, 0, nums2.length - 1,
(nums1.length + nums2.length + 2) / 2);
//如果是奇数，则两次求的 k 都是一样的，即(nums1.length + nums2.length + 1) / 2
== (nums1.length + nums2.length + 2) / 2
return (ans1 + ans2) / 2.0;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int
end2, int k) {
int siz1 = end1 - start1 + 1;
int siz2 = end2 - start2 + 1;
if (siz1 > siz2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
//为了方便知道哪个数组首先为空，我们设置 siz1 严格小于等于 siz2，这样子一旦有数组
被清空，则一定是 nums1
if (siz1 == 0) return nums2[start2 + k - 1];//已经把第一个数组全部排除，只需要求
第二数组的剩下数字中的第 k 个就行了（更新后的 k）
if (k == 1) return Math.min(nums1[start1], nums2[start2]);//求当前两个数组中
最小的数字，当然直接返回两个当前中最小的即可
int pos1 = start1 + Math.min(siz1, k / 2) - 1;
int pos2 = start2 + Math.min(siz2, k / 2) - 1;
if (nums1[pos1] > nums2[pos2])
return getKth(nums1, start1, end1, nums2, pos2 + 1, end2, k - (pos2 -
start2 + 1));//排除第二个数组不符合条件的数字
else
return getKth(nums1, pos1 + 1, end1, nums2, start2, end2, k - (pos1 -
start1 + 1));//排除第一个数组不符合条件的数字
}
}
当输入是 nums1 = [2,5,8] 和 nums2 = [3,4,5,6,7,8,9,10] 时，我们来模拟一下整个题解
的过程：
1. 计算中位数的位置：
– nums1.length = 3, nums2.length = 8，总长度 n + m = 11。
– 由于 11 是奇数，中位数是合并后数组中的第 (11 + 1) / 2 = 6 个元素。
2. 第一次调用 **getKth**** 方法**：
– 寻找第 6 小的元素，调用 getKth(nums1, 0, 2, nums2, 0, 7, 6)。
3. 递归查找中位数：
– 在 getKth 方法中，我们会不断递归缩小 k 的值，直到找到第 k 小的数。
– 对于第一次调用，我们比较 nums1[2] (8) 和 nums2[2] (5)。由于 8 > 5，我们
可以确定在 nums2[0..2] 中没有第 6 小的数，这些元素可以被排除。
– 更新 k 的值：k = 6 - 3 = 3 (排除了 3 个元素)。
– 继续递归。
4. 找到中位数：
– 最后找到中位数是 6.0。
如果还不明白的话，可以利用 ACM 输入输出的格式在 Intellij IDEA 中进行 debug 调试。
public class Main004 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("输入第一个数组");
// 读取一串字符，按照, 分割成 int 型数组
String[] nums1Str = scanner.nextLine().split(",");
int[] nums1 = new int[nums1Str.length];
for (int i = 0; i < nums1Str.length; i++) {
nums1[i] = Integer.parseInt(nums1Str[i]);
}
System.out.println("输入第二个数组");
// 读取一串字符，按照, 分割成 int 型数组
String[] nums2Str = scanner.nextLine().split(",");
int[] nums2 = new int[nums2Str.length];
for (int i = 0; i < nums2Str.length; i++) {
nums2[i] = Integer.parseInt(nums2Str[i]);
}
Solution004 solution = new Solution004();
double median = solution.findMedianSortedArrays(nums1, nums2);
System.out.println("中位数是: " + median);
}
}
class Solution004 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int ans1 = getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1,
(nums1.length + nums2.length + 1) / 2);
int ans2 = getKth(nums1,0, nums1.length - 1, nums2, 0, nums2.length - 1,
(nums1.length + nums2.length + 2) / 2);
//如果是奇数，则两次求的 k 都是一样的，即(nums1.length + nums2.length + 1) / 2
== (nums1.length + nums2.length + 2) / 2
return (ans1 + ans2) / 2.0;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int
end2, int k) {
int siz1 = end1 - start1 + 1;
int siz2 = end2 - start2 + 1;
if (siz1 > siz2) {
return getKth(nums2, start2, end2, nums1, start1, end1, k);
}
//为了方便知道哪个数组首先为空，我们设置 siz1 严格小于等于 siz2，这样子一旦有数组
被清空，则一定是 nums1
if (siz1 == 0) {
return nums2[start2 + k - 1];//已经把第一个数组全部排除，只需要求第二数组的
剩下数字中的第 k 个就行了（更新后的 k）
}
if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);//求当前两个数组中最小的数
字，当然直接返回两个当前中最小的即可
}
int pos1 = start1 + Math.min(siz1, k / 2) - 1;
int pos2 = start2 + Math.min(siz2, k / 2) - 1;
if (nums1[pos1] > nums2[pos2]) {
//排除第二个数组不符合条件的数字
return getKth(nums1, start1, end1, nums2, pos2 + 1, end2, k - (pos2 -
start2 + 1));
}
else {
//排除第一个数组不符合条件的数字
return getKth(nums1, pos1 + 1, end1, nums2, start2, end2, k - (pos1 -
start1 + 1));
}
}
}
完整的跑一次就能明白了。
004.%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E
6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0-
20231213234453.png
时间复杂度：$ O((n+m)) $
第一次，我们排除了(n + m) / 2 / 2 个数字
第二次，我们排除了(n + m) / 2 / 2 / 2 个数字
$$
最终我们排除了$ (n+m) $次，终于把`(n + m) / 2 - 1`个数字全都排除完了，所以时间复杂
度是$ O((n+m)) $
轻松打败 100% 用户。
004.%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%AD%A3%E5%BA%8F%E
6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0-
20231213182055.png
总结
本次题解我们一共经历了三个重大的思维转变：
1. 暴力解法，时间复杂度为 $ O((n+m) ) $。
2. 归并排序，时间复杂度为 $ O(n+m) $。
3. 二分查找结合寻找第 K 小的数，时间复杂度为 $ O() $。
涉及到知识点也比较多，大部分在《二哥的 Java 进阶之路》上都能找到，比如说：
• 数组复制
• 位运算
• 取模运算
• 归并排序
• 二分查找
• 寻找第 K 小的数
力扣链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/