题目:寻找两个正序数组的中位数
给定两个大小分别为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
-10^6 <= nums1[i], nums2[i] <= 10^6- 进阶：
你能设计一个时间复杂度为 O(log₂(m+n)) 的算法解决此问题吗？思路1
把两个数组合并为一个大数组,然后对合并后的数组进行排序,最后根据奇数，还是偶数，返回中位数。
- 时间复杂度:O(m+n)
- 空间复杂度:O(m+n)
代码
public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 时间复杂度：O(m+n)
// 新建一个大数组num3,长度为nums1.length + nums2.length,用来将两个数组合并为一个数组
int[] nums3 = new int[nums1.length + nums2.length]; // 空间复杂度:O(m+n)
// 将num1中元素添加到num3中
for (int i = 0; i < nums1.length; i++) { // 时间复杂度：O(m)
nums3[i] = nums1[i];
}
// 将num2中元素添加到num3中
for (int i = 0; i < nums2.length; i++) { // 时间复杂度：O(n)
nums3[nums1.length + i] = nums2[i];
}
// 对大数组num3进行排序
Arrays.sort(nums3); // 时间复杂度O(log₂n)
if (nums3.length % 2 == 0) { // 如果合并后数组长度是偶数,返回中间两个数的平均值
int mid1 = nums3.length / 2;
int mid2 = nums3.length / 2 - 1;
return nums3[mid1] + nums3[mid2] / 2.0; // 求平均数，注意要除2.0，否则会下取整
} else { // 如果合并后数组长度是奇数,返回中间的那个数
int mid = nums3.length / 2;
return nums3[(mid)];
}
}思路2
用双指针,最开始两个指针分别指向两个数组的起始位置。
然后写一个循环,两个指针谁指向的值小,哪个指针右移一位,然后判断是否到了中位数的位置，到了就返回结果。
返回中位数的话，奇数需要最后一次遍历的结果就可以了，偶数需要最后一次和上一次遍历的结果。所以我们用两个变量left和right，right保存当前循环的结果，在每次循环前将right的值赋给left。这样在最后一次循环的时候，left将得到right的值，也就是上一次循环的结果，接下来 right更新为最后一次的结果。
- 时间复杂度:O(m+n)
- 空间复杂度:O(1)
代码
public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 时间复杂度：O(m+n)
int m = nums1.length;
int n = nums2.length;
int len = m + n;
int left = 0, right = 0;
// 第一个指针指向num1起始位置,第二个指针指向num2起始位置
int num1Start = 0, num2Start = 0;
for (int i = 0; i <= len / 2; i++) { // 时间复杂度：O(m+n)
// left为right上一次遍历的结果
left = right;
// 如果指针1没有越界且指针2已经越界了 或 指针1没有越界且指针1指向的值小于指针2指向的值
if (num1Start < m && (num2Start >= n || nums1[num1Start] < nums2[num2Start])) {
right = nums1[num1Start++];
} else {
right = nums2[num2Start++];
}
}
if ((len % 2) == 0) {
// 如果合并后数组长度是偶数,返回中间两个数的平均值
return (left + right) / 2.0; // 求平均数，注意要除2.0，否则会下取整
} else {
// 如果合并后数组长度是奇数,返回中间的那个数
return right;
}
}思路3
上边的两种思路，时间复杂度都达不到题目的要求O(log(m+n)。看到log，很明显，我们只有用到二分的方法才能达到。我们不妨用另一种思路，题目是求中位数，其实就是求第k小数的一种特殊情况，而求第 k小数有一种算法。
可以参考这个链接:
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/di-k-xiao-shu-jie-fa-ni-zhen-de-dong-ma-by-geek-8m/
- 时间复杂度:O(log₂(m+n))
- 空间复杂度:O(1)
代码
public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 总时间复杂度:O(log(m+n)
// 求出两个数组的总长度
int length = nums1.length + nums2.length;
// 如果是偶数，则求出中间两个数的平均数
if (length % 2 == 0) {
int mid1 = find(nums1, 0, nums2, 0, length / 2);
int mid2 = find(nums1, 0, nums2, 0, length / 2 + 1);
return (mid1 + mid2) / 2.0; // 求平均数，注意要除2.0，否则会下取整
} else {
return find(nums1, 0, nums2, 0, length / 2 + 1);
}
}
/**
* 方法用途:求num1和num2中第k小的数
* 参数: nums1, nums2: 两个数组
* left1, left2分别为nums1, nums2的起始位置
* k为要求的第K小的数
**/
public int find(int[] nums1, int left1, int[] nums2, int left2, int k) {
int length1 = nums1.length;
int length2 = nums2.length;
// 为了方便，我们使nums1的长度小于nums2的长度
if (length1 - left1 > length2 - left2) {
return find(nums2, left2, nums1, left1, k);
}
// 如果nums1的起始位置已经与其长度相等，则nums1中的数已经用光了，返回nums2中第K小的数
if (left1 == length1) {
return nums2[left2 - 1 + k];
}
// 如果k等于1，则相当与求出两个数组中的最小值，直接返回nums1[left1], nums2[left2]中较小的一个
if (k == 1) {
return Math.min(nums1[left1], nums2[left2]);
}
// si表示[k / 2]后面的那个数的下标。
// 此处si与nums1的长度取最小值，因为可能会出现left1 + k / 2 > num1.length的情况
int si = left1 + Math.min(length1, k / 2);
// sj表示[k / 2]后面的那个数的下标。
// 此处sj与nums2的长度取最小值，因为可能会出现left2 + k / 2 > num2.length的情况
int sj = left2 + Math.min(length2, k / 2);
if (nums1[si - 1] > nums2[sj - 1]) {
// 由于去除了从left2到sj之间的数，所以原本的第K小的数在新数组中为第k - (sj - left2)小的数
return find(nums1, left1, nums2, sj, k - (sj - left2));
} else {
// 由于去除了从left1到si之间的数，所以原本的第K小的数在新数组中为第k - (si - left1)小的数
return find(nums1, si, nums2, left2, k - (si - left1));
}
}
