题目
寻找两个正序数组的中位数。
示例 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
- -106 <= nums1[i], nums2[i] <= 106
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
思路
给定两个有序数组，要求找到两个有序数组的中位数，最直观的思路有以下两种：
-
使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。
-
不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。
思路1
简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。
复杂度分析
时间复杂度：遍历全部数组 O(m+n)
空间复杂度：开辟了一个数组，保存合并后的两个数组 O(m+n)
代码
public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
}
优化
本题最容易想到的思路应该是双指针线性扫描两个数组，时间复杂度为(m + n)，不符合进阶要求。现提供log(m + n)的解法如下：
我们知道，快速选择出数组中第K个数的快速选择算法使用了分治的思想，本题的思想与之类似，都是将问题拆解为一个个的子问题，然后分别处理。
- 首先，求中位数要先看数组的总长度，如果为偶数，则中位数是中间两个数的平均值((nums[length / 2] + nums[length / 2 + 1]) / 2)；如果为奇数，则中位数为最中间的数(nums[length / 2 + 1]).
- 如果直接递归求解中位数，不太容易找到思路，我们可以选择一种更通用的解法，即找出两个数组中第k小的元素，然后按照上面所说的求中位数的方法得到中位数
那么如何求出两个数组中第k小的数？我们考虑先分别求出两个数组中第k/2个元素(由于数组是有序的，所以取出的元素在原数组中是第k/2小的元素)。然后有三种情况：
我们假设第一个数组为A，第二个数组为B
<mark>1. A[k / 2] < B[k / 2]</mark>
- 因为两个数组都是有序的，所以在A数组中，A[0] ~ A[k / 2 - 1]都要小于等于A[k / 2]，也就是说在数组A中有 k / 2 个元素要小于等于A[k / 2](包括A[k / 2])
- 而在B数组中，由于B[k / 2] > A[k / 2], 所以B数组前 k / 2 个元素中，小于等于A[k / 2]的最多有 k / 2 - 1个(极限情况，即只有B[k / 2]要大于A[k / 2]，而B[0] ~ B[k / 2 - 1]都要小于A[k / 2]).
- 两个数组中小于等于A[k / 2]的数为A数组中 k / 2个，B数组中最多 k / 2 - 1 个，一共最多有k - 1个数小于等于A[k / 2]，所以A数组中从A[0] ~ A[k / 2]这些数都不可能是第K个数
- 这样我们就将问题变为了在剩下的数中寻找第(k - k / 2(下取整))小的值
<mark>2. A[k / 2] > B[k / 2]</mark>
- 分析过程同上，可以得出B数组中从B[0] ~ B[k / 2]这些数都不可能是第K个数
<mark>3. A[k / 2] = B[k / 2]</mark>
0 A数组中小于等于A[k / 2]的数有 k / 2 - 1个(去除A[k / 2])，B数组中小于等于B[k / 2]的数有 k / 2 - 1个(去除B[k / 2])，然后加上A[k / 2], B[k / 2]，刚刚好有K个数小于等于A[k / 2](或B[k / 2])，所以第K小的数恰好就是A[k / 2](或B[k / 2]，二者相等)
这样，我们每次都可以排除掉k / 2个数，而K的值最多减到1，即找到两个数组中第1小的值(即两个数组中的最小值)，这样我们就找到了递归的基础情况。
<mark>有以下三种情况需要特殊处理</mark>：
-
如果A[k/2-1]或者 B[k/2−1] 越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 k 的值，而不能直接将 k 减去 k/2。
-
如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。
-
如果 k=1，我们只要返回两个数组首元素的最小值即可
代码
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int totalLength = length1 + length2;
if (totalLength % 2 == 1) {
int midIndex = totalLength / 2;
double median = getKthElement(nums1, nums2, midIndex + 1);
return median;
} else {
int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
return median;
}
}
public int getKthElement(int[] nums1, int[] nums2, int k) {
/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
*/
int length1 = nums1.length, length2 = nums2.length;
int index1 = 0, index2 = 0;
int kthElement = 0;
while (true) {
// 边界情况
if (index1 == length1) {
return nums2[index2 + k - 1];
}
if (index2 == length2) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
// 正常情况
int half = k / 2;
int newIndex1 = Math.min(index1 + half, length1) - 1;
int newIndex2 = Math.min(index2 + half, length2) - 1;
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}
进一步优化
现在我们有两个数组：num1: [a1,a2,a3,…an] ,nums2: [b1,b2,b3,…bn]
[nums1[left1],nums2[left2] | nums1[right1], nums2[right2]]
只要保证左右两边个数相同，中位数就在 | 这个边界旁边产生。
如何找边界值，我们可以用二分法，我们先确定 num1 取 m1 个数的左半边，那么 num2 取 m2 = (m+n+1)/2 - m1 的左半边，找到合适的 m1，就用二分法找。
当 [ [a1],[b1,b2,b3] | [a2,…an],[b4,…bn] ]
我们只需要比较 b3 和 a2 的关系的大小，就可以知道这种分法是不是准确的！
例如：我们令：
nums1 = [-1,1,3,5,7,9]
nums2 =[2,4,6,8,10,12,14,16]
当 m1 = 4,m2 = 3 ,它的中位数就是median = (num1[m1] + num2[m2])/2
代码
public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if(m > n){
return findMedianSortedArrays(nums2,nums1);
//让 nums1 的长度小于 nums2，这样就能保证如果有数组空了，一定是 nums1
}
int nums1Left = 0, nums1Right = m;
// median1：前一部分的最大值
// median2：后一部分的最小值
int median1 = 0, median2 = 0;
while (nums1Left <= nums1Right){
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
int nums1Center = (nums1Left + nums1Right) / 2;
int nums2Center = (m + n + 1) / 2 - nums1Center;
// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[nums1Center-1], nums1[nums1Center], nums2[nums2Center-1], nums2[nums2Center]
int nums_im1 = (nums1Center == 0 ? Integer.MIN_VALUE : nums1[nums1Center - 1]);
int nums_i = (nums1Center == m ? Integer.MAX_VALUE : nums1[nums1Center]);
int nums_jm1 = (nums2Center == 0 ? Integer.MIN_VALUE : nums2[nums2Center - 1]);
int nums_j = (nums2Center == n ? Integer.MAX_VALUE : nums2[nums2Center]);
//当一个数组不出现在前一部分时，对应的值为负无穷，
//就不会对前一部分的最大值产生影响；当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。
if (nums_im1 <= nums_j) {
median1 = Math.max(nums_im1, nums_jm1);
median2 = Math.min(nums_i, nums_j);
nums1Left = nums1Center + 1;
} else {
nums1Right = nums1Center - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
其中 m 和 n 分别是数组nums1和 nums2 的长度。查找的区间是 [0, m]，而该区间的长度在每次循环之后都会减少为原来的一半。所以，只需要执行logm次循环。由于每次循环中的操作次数是常数，所以时间复杂度为O(logm)。由于我们可能需要交换nums1和 nums2，使得 m<= n ，因此
时间复杂度：O(log(min(m,n)))
作者：LeetCode-Solution
来源：力扣（LeetCode）
本公众号分享自己从程序员小白到经历春招秋招斩获10几个offer的面试笔试经验，其中包括【Java】、【操作系统】、【计算机网络】、【设计模式】、【数据结构与算法】、【大厂面经】、【数据库】期待你加入！！！
1.计算机网络----三次握手四次挥手
2.梦想成真-----项目自我介绍
3.你们要的设计模式来了
4.震惊！来看《这份程序员面试手册》！！！
5.一字一句教你面试“个人简介”
6.接近30场面试分享
7.你们要的免费书来了
京公网安备 11010502036488号