寻找两个正序数组的中位数
难度:
标签:
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 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
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
代码结果
运行时间: 48 ms, 内存: 15 MB
/*
* 思路：
* 1. 使用Java Stream API来合并两个数组并找到中位数。
* 2. 我们可以将两个数组转换为IntStream，然后使用sorted()对它们进行排序。
* 3. 然后我们计算中位数，处理总长度为奇数和偶数的情况。
*/
import java.util.stream.IntStream;
import java.util.Arrays;
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] merged = IntStream.concat(Arrays.stream(nums1), Arrays.stream(nums2))
.sorted()
.toArray();
int len = merged.length;
if (len % 2 == 0) { // 如果总长度是偶数，中位数是中间两个数的平均值
return (merged[len / 2 - 1] + merged[len / 2]) / 2.0;
} else { // 如果总长度是奇数，中位数是中间的数
return merged[len / 2];
}
}
}解释
方法:
该题解使用了二分查找的思想。首先确保较短的数组为 nums1，如果不是就交换。然后使用二分查找在 nums1 中找到一个分割点 i，使得 nums1[0...i-1] 和 nums2[0...j-1]（j = (m+n+1)//2 - i）的元素个数之和等于 (m+n+1)//2。这样就可以保证左半部分的元素个数等于右半部分或者多一个。最后，根据总元素个数的奇偶性，返回左半部分的最大值或左右部分的最大最小值的平均数作为中位数。
时间复杂度:
O(log min(m, n))
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到，首先确保较短的数组为 `nums1`，这样做的目的是什么？
▷🦆
为什么在二分查找时，`i` 的更新方式是 `i = l + (r - l + 1) // 2` 而不是 `i = (l + r) // 2`？
▷🦆
在比较 `nums1[i-1]` 和 `nums2[j]` 时，为什么使用的是 `nums1[i-1] <= nums2[j]` 而不是 `nums1[i] <= nums2[j-1]`？
▷🦆
题解中提到，返回的中位数是根据总元素个数的奇偶性来确定的。这种做法的原理是什么？
▷