我每天都在读《二哥的 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