004.寻找两个正序数组的中位数

作者：沉默王二 发布时间：2023-12-14T09:11:24.568+0800

---

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 技术派专栏地址：https://paicoding.com/column/7/ 4

• 星球原地址：https://t.zsxq.com/155IWCJEm

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

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

------------------------by鲁迅

题意

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

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

示例

输入：nums1=[1,3],nums2=[2]

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

输入：nums1=[1,2],nums2=[3,4]

解释：合并数组=[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[] 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 {

    // 创建一个新数组，长度为两个数组长度之和        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(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]。
• 继续合并其他子数组。
• 最后，将所有合并的子数组合并为最终的排序数组。

它每一层的拆分都是对半的，所以时间复杂度是，而每一层的合并都是对两个数组的合并，所以时间复杂度是，所以整体的时间复杂度是。

分解步骤涉及将数组递归地分成两半，直到每个子数组只包含一个元素。对于长度为 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 {

    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] 时，我们来模拟整个题解过程：

• 初始化：
• nums1 的长度 n = 2，nums2 的长度 m = 2。
• 总长度 n + m = 4，所以总长度是偶数，flag = true。
• 设置两个数组的指针 point1 = 0，point2 = 0。
• 初始化 remNum1 和 remNum2 为 0，用来存储当前元素和前一个元素。
• 开始遍历数组：
• 第一次循环（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。
• 计算中位数：
• 因为总长度是偶数（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。

• point1 < n：
• 这是检查 nums1 的指针 point1 是否还在数组的范围内。如果 point1 已经等于 n，意味着 nums1 中的所有元素都已经被考虑过了。
• point2 >= m：
• 这是检查 nums2 的指针 point2 是否超出了数组的范围。如果 point2 大于或等于 m，意味着 nums2 中的所有元素都已经被考虑过了。
• nums1[point1] < nums2[point2]
• 这是比较 nums1 和 nums2 当前指针位置的元素。如果 nums1 当前元素小于 nums2 当前元素，这个条件成立。

在合并两个排序数组时，我们希望按照排序顺序依次选取两个数组中的元素。这个条件帮助我们决定接下来应该选取 nums1 还是 nums2 中的元素：

• 当 nums1 还有元素，并且 nums2 要么已经处理完，要么 nums1 的当前元素更小，我们就选择 nums1 的当前元素。
• 如果条件不成立（即 nums1 处理完了，或者 nums1 的当前元素不小于 nums2 的当前元素），我们就从 nums2 中选取元素。

这样的逻辑确保了合并后的数组是有序的，同时也高效地利用了两个已排序数组的性质。

时间复杂度：，归并到中位数：O(m + n)，每次从两个数组的开头取较小的数，直到达到中位数的位置。

但题目要求的是 。

分析 3

根据中位数的定义，当数组长度为奇数时，中位数就是数组中的第(size + 1) / 2个，偶数的话，则是第(size + 1) / 2个数和第(size + 1) / 2 + 1个数的平均数。

来看这样子一组样例(从第一个开始计数)

nums1:[2,5,8]

合并后：[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 个元素的值来决定如何继续搜索。

什么是二分查找法？

二分查找法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

比如说 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 肯定不行，对吧？

所以我们可以把 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 肯定不行，对吧？

那把 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 {

    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] 时，我们来模拟一下整个题解的过程：

• 计算中位数的位置：
• nums1.length = 3, nums2.length = 8，总长度 n + m = 11。
• 由于 11 是奇数，中位数是合并后数组中的第 (11 + 1) / 2 = 6 个元素。
• 第一次调用 getKth 方法：
• 寻找第 6 小的元素，调用 getKth(nums1, 0, 2, nums2, 0, 7, 6)。
• 递归查找中位数：
• 在 getKth 方法中，我们会不断递归缩小 k 的值，直到找到第 k 小的数。
• 对于第一次调用，我们比较 nums1[2] (8) 和 nums2[2] (5)。由于 8 > 5，我们可以确定在 nums2[0..2] 中没有第 6 小的数，这些元素可以被排除。
• 更新 k 的值：k = 6 - 3 = 3 (排除了 3 个元素)。
• 继续递归。
• 找到中位数：
• 最后找到中位数是 6.0。

如果还不明白的话，可以利用 ACM 输入输出的格式在 Intellij IDEA 中进行 debug 调试。

public class Main004 {

    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)); } }}

完整的跑一次就能明白了。

时间复杂度：

第一次，我们排除了(n + m) / 2 / 2个数字

第二次，我们排除了(n + m) / 2 / 2 / 2 个数字

最终我们排除了次，终于把(n + m) / 2 - 1个数字全都排除完了，所以时间复杂度是

轻松打败 100% 用户。

总结

本次题解我们一共经历了三个重大的思维转变：

• 暴力解法，时间复杂度为 。
• 归并排序，时间复杂度为 。
• 二分查找结合寻找第 K 小的数，时间复杂度为 。

涉及到知识点也比较多，大部分在《二哥的 Java 进阶之路》上都能找到，比如说：

• 数组复制
• 位运算
• 取模运算
• 归并排序
• 二分查找
• 寻找第 K 小的数

力扣链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

    - 语雀专栏地址+密码可通过星球置顶帖查看：[https://t.zsxq.com/15rEo9Pdu](https://t.zsxq.com/15rEo9Pdu)

• 技术派专栏地址：https://paicoding.com/column/7/ 4

• 星球原地址：https://t.zsxq.com/155IWCJEm

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

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

------------------------by鲁迅

题意

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

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

示例

输入：nums1=[1,3],nums2=[2]

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

输入：nums1=[1,2],nums2=[3,4]

解释：合并数组=[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[] 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 {

    // 创建一个新数组，长度为两个数组长度之和        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(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]。
• 继续合并其他子数组。
• 最后，将所有合并的子数组合并为最终的排序数组。

它每一层的拆分都是对半的，所以时间复杂度是，而每一层的合并都是对两个数组的合并，所以时间复杂度是，所以整体的时间复杂度是。

分解步骤涉及将数组递归地分成两半，直到每个子数组只包含一个元素。对于长度为 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 {

    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] 时，我们来模拟整个题解过程：

• 初始化：
• nums1 的长度 n = 2，nums2 的长度 m = 2。
• 总长度 n + m = 4，所以总长度是偶数，flag = true。
• 设置两个数组的指针 point1 = 0，point2 = 0。
• 初始化 remNum1 和 remNum2 为 0，用来存储当前元素和前一个元素。
• 开始遍历数组：
• 第一次循环（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。
• 计算中位数：
• 因为总长度是偶数（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。

• point1 < n：
• 这是检查 nums1 的指针 point1 是否还在数组的范围内。如果 point1 已经等于 n，意味着 nums1 中的所有元素都已经被考虑过了。
• point2 >= m：
• 这是检查 nums2 的指针 point2 是否超出了数组的范围。如果 point2 大于或等于 m，意味着 nums2 中的所有元素都已经被考虑过了。
• nums1[point1] < nums2[point2]
• 这是比较 nums1 和 nums2 当前指针位置的元素。如果 nums1 当前元素小于 nums2 当前元素，这个条件成立。

在合并两个排序数组时，我们希望按照排序顺序依次选取两个数组中的元素。这个条件帮助我们决定接下来应该选取 nums1 还是 nums2 中的元素：

• 当 nums1 还有元素，并且 nums2 要么已经处理完，要么 nums1 的当前元素更小，我们就选择 nums1 的当前元素。
• 如果条件不成立（即 nums1 处理完了，或者 nums1 的当前元素不小于 nums2 的当前元素），我们就从 nums2 中选取元素。

这样的逻辑确保了合并后的数组是有序的，同时也高效地利用了两个已排序数组的性质。

时间复杂度：，归并到中位数：O(m + n)，每次从两个数组的开头取较小的数，直到达到中位数的位置。

但题目要求的是 。

分析 3

根据中位数的定义，当数组长度为奇数时，中位数就是数组中的第(size + 1) / 2个，偶数的话，则是第(size + 1) / 2个数和第(size + 1) / 2 + 1个数的平均数。

来看这样子一组样例(从第一个开始计数)

nums1:[2,5,8]

合并后：[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 个元素的值来决定如何继续搜索。

什么是二分查找法？

二分查找法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

比如说 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 肯定不行，对吧？

所以我们可以把 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 肯定不行，对吧？

那把 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 {

    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] 时，我们来模拟一下整个题解的过程：

• 计算中位数的位置：
• nums1.length = 3, nums2.length = 8，总长度 n + m = 11。
• 由于 11 是奇数，中位数是合并后数组中的第 (11 + 1) / 2 = 6 个元素。
• 第一次调用 getKth 方法：
• 寻找第 6 小的元素，调用 getKth(nums1, 0, 2, nums2, 0, 7, 6)。
• 递归查找中位数：
• 在 getKth 方法中，我们会不断递归缩小 k 的值，直到找到第 k 小的数。
• 对于第一次调用，我们比较 nums1[2] (8) 和 nums2[2] (5)。由于 8 > 5，我们可以确定在 nums2[0..2] 中没有第 6 小的数，这些元素可以被排除。
• 更新 k 的值：k = 6 - 3 = 3 (排除了 3 个元素)。
• 继续递归。
• 找到中位数：
• 最后找到中位数是 6.0。

如果还不明白的话，可以利用 ACM 输入输出的格式在 Intellij IDEA 中进行 debug 调试。

public class Main004 {

    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)); } }}

完整的跑一次就能明白了。

时间复杂度：

第一次，我们排除了(n + m) / 2 / 2个数字

第二次，我们排除了(n + m) / 2 / 2 / 2 个数字

最终我们排除了次，终于把(n + m) / 2 - 1个数字全都排除完了，所以时间复杂度是

轻松打败 100% 用户。

总结

本次题解我们一共经历了三个重大的思维转变：

• 暴力解法，时间复杂度为 。
• 归并排序，时间复杂度为 。
• 二分查找结合寻找第 K 小的数，时间复杂度为 。

涉及到知识点也比较多，大部分在《二哥的 Java 进阶之路》上都能找到，比如说：

• 数组复制
• 位运算
• 取模运算
• 归并排序
• 二分查找
• 寻找第 K 小的数

力扣链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

    - 语雀专栏地址+密码可通过星球置顶帖查看：[https://t.zsxq.com/15rEo9Pdu](https://t.zsxq.com/15rEo9Pdu)

• 技术派专栏地址：https://paicoding.com/column/7/ 4

• 星球原地址：https://t.zsxq.com/155IWCJEm

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

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

------------------------by鲁迅

题意

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

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

示例

输入：nums1=[1,3],nums2=[2]

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

输入：nums1=[1,2],nums2=[3,4]

解释：合并数组=[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[] 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 {

    // 创建一个新数组，长度为两个数组长度之和        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(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]。
• 继续合并其他子数组。
• 最后，将所有合并的子数组合并为最终的排序数组。

它每一层的拆分都是对半的，所以时间复杂度是，而每一层的合并都是对两个数组的合并，所以时间复杂度是，所以整体的时间复杂度是。

分解步骤涉及将数组递归地分成两半，直到每个子数组只包含一个元素。对于长度为 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 {

    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] 时，我们来模拟整个题解过程：

• 初始化：
• nums1 的长度 n = 2，nums2 的长度 m = 2。
• 总长度 n + m = 4，所以总长度是偶数，flag = true。
• 设置两个数组的指针 point1 = 0，point2 = 0。
• 初始化 remNum1 和 remNum2 为 0，用来存储当前元素和前一个元素。
• 开始遍历数组：
• 第一次循环（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。
• 计算中位数：
• 因为总长度是偶数（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。

• point1 < n：
• 这是检查 nums1 的指针 point1 是否还在数组的范围内。如果 point1 已经等于 n，意味着 nums1 中的所有元素都已经被考虑过了。
• point2 >= m：
• 这是检查 nums2 的指针 point2 是否超出了数组的范围。如果 point2 大于或等于 m，意味着 nums2 中的所有元素都已经被考虑过了。
• nums1[point1] < nums2[point2]
• 这是比较 nums1 和 nums2 当前指针位置的元素。如果 nums1 当前元素小于 nums2 当前元素，这个条件成立。

在合并两个排序数组时，我们希望按照排序顺序依次选取两个数组中的元素。这个条件帮助我们决定接下来应该选取 nums1 还是 nums2 中的元素：

• 当 nums1 还有元素，并且 nums2 要么已经处理完，要么 nums1 的当前元素更小，我们就选择 nums1 的当前元素。
• 如果条件不成立（即 nums1 处理完了，或者 nums1 的当前元素不小于 nums2 的当前元素），我们就从 nums2 中选取元素。

这样的逻辑确保了合并后的数组是有序的，同时也高效地利用了两个已排序数组的性质。

时间复杂度：，归并到中位数：O(m + n)，每次从两个数组的开头取较小的数，直到达到中位数的位置。

但题目要求的是 。

分析 3

根据中位数的定义，当数组长度为奇数时，中位数就是数组中的第(size + 1) / 2个，偶数的话，则是第(size + 1) / 2个数和第(size + 1) / 2 + 1个数的平均数。

来看这样子一组样例(从第一个开始计数)

nums1:[2,5,8]

合并后：[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 个元素的值来决定如何继续搜索。

什么是二分查找法？

二分查找法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

比如说 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 肯定不行，对吧？

所以我们可以把 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 肯定不行，对吧？

那把 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 {

    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] 时，我们来模拟一下整个题解的过程：

• 计算中位数的位置：
• nums1.length = 3, nums2.length = 8，总长度 n + m = 11。
• 由于 11 是奇数，中位数是合并后数组中的第 (11 + 1) / 2 = 6 个元素。
• 第一次调用 getKth 方法：
• 寻找第 6 小的元素，调用 getKth(nums1, 0, 2, nums2, 0, 7, 6)。
• 递归查找中位数：
• 在 getKth 方法中，我们会不断递归缩小 k 的值，直到找到第 k 小的数。
• 对于第一次调用，我们比较 nums1[2] (8) 和 nums2[2] (5)。由于 8 > 5，我们可以确定在 nums2[0..2] 中没有第 6 小的数，这些元素可以被排除。
• 更新 k 的值：k = 6 - 3 = 3 (排除了 3 个元素)。
• 继续递归。
• 找到中位数：
• 最后找到中位数是 6.0。

如果还不明白的话，可以利用 ACM 输入输出的格式在 Intellij IDEA 中进行 debug 调试。

public class Main004 {

    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)); } }}

完整的跑一次就能明白了。

时间复杂度：

第一次，我们排除了(n + m) / 2 / 2个数字

第二次，我们排除了(n + m) / 2 / 2 / 2 个数字

最终我们排除了次，终于把(n + m) / 2 - 1个数字全都排除完了，所以时间复杂度是

轻松打败 100% 用户。

总结

本次题解我们一共经历了三个重大的思维转变：

• 暴力解法，时间复杂度为 。
• 归并排序，时间复杂度为 。
• 二分查找结合寻找第 K 小的数，时间复杂度为 。

涉及到知识点也比较多，大部分在《二哥的 Java 进阶之路》上都能找到，比如说：

• 数组复制
• 位运算
• 取模运算
• 归并排序
• 二分查找
• 寻找第 K 小的数

力扣链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412