二哥的 LeetCode 刷题笔记：004.寻找两个正序数组的中位数
我每天都在读《二哥的 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。
2人已点赞
回复