LeetCode.004.Median of Two Sorted Arrays 两个有序数组的中位数
题目描述
004 Median of Two Sorted Arrays
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).
Example 1:*
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
解题过程
O(m+n)归并排序法
我只会简单的归并排序法，写了一版，通过了，速度还不慢，打败了93%：
时间复杂度 O(m+n)，空间复杂度 O(m+n)
// 归并排序法
private static class SolutionV2018 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length + nums2.length];
int i = 0, j = 0, k = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] <= nums2[j]) {
res[k++] = nums1[i++];
} else {
res[k++] = nums2[j++];
}
}
while (i < nums1.length) {
res[k++] = nums1[i++];
}
while (j < nums2.length) {
res[k++] = nums2[j++];
}
return res.length % 2 == 0 ? (double) (res[res.length / 2] + res[(res.length / 2) - 1]) / 2 : res[res.length / 2];
}
}
O(m+n)双指针计数第(m+n)/2个元素
还是归并的思想，但不需要真正做归并，中位数一定是两个数组的从前往后数第 (m+n)/2+1 个元素
若 m+n 是奇数，中位数是单个数，即第 (m+n)/2 + 1 个元素
若 m+n 是偶数，中位数是两个数，即第 (m+n)/2 和 第 (m+n)/2 + 1 个元素
用两个指针 i,j 分别从前往后遍历 nums1 和 nums2，哪个指针的元素值小就往后移动，并计数，遍历过程中用 preMediam 记录前一个元素，用于记录当 m+n 是偶数时的第一个中位数。
当数到第 (m+n)/2 + 1 个元素时，停止，根据 (m+n) 的奇偶性决定是返回 median 还是 (preMedian + median) / 2
相比于归并排序法，空间复杂度降为 O(1)
时间复杂度 O(m+n)，空间复杂度 O(1)
// 中位数一定是两个数组的从前往后数第 (m+n)/2 个元素
private static class SolutionV202005Count {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 若 m+n 是奇数，中位数是单个数，即第 (m+n)/2 + 1 个元素
// 若 m+n 是偶数，中位数是两个数，即第 (m+n)/2 和 第 (m+n)/2 + 1 个元素
int medianCount = (nums1.length + nums2.length)/2 +1;
// preMedian 是第 (m+n)/2 个元素，即当 m+n 是偶数时的第一个中位数
int preMedian = 0, median = 0;
int i = 0, j = 0;
int count = 0; // 遍历的元素个数
while (i < nums1.length || j < nums2.length) {
if (i < nums1.length && j < nums2.length) {
median = (nums1[i] < nums2[j]) ? nums1[i++] : nums2[j++];
} else {
median = (i == nums1.length) ? nums2[j++] : nums1[i++];
}
count++;
if (count == medianCount) {
break;
}
preMedian = median;
}
return (nums1.length + nums2.length) % 2 == 1 ? median : (double)(preMedian + median) / 2;
}
}
O(log(m+n))二分搜索找第k小元素
要是面试的话，这时候肯定要问怎么优化了，看到复杂度要求为 O(log(m+n))，能想到肯定用二分、二叉来解决。
这道题转化为 求两个有序数组的第 k 小元素 问题，其中 k = (m+n)/2+1，可以通过二分搜索解决，当然如果 m+n 是偶数时需要求第 k-1 小和第 k 小的数。
这里的二分比较难理解，和普通的二分搜索不一样，普通二分搜索是对数组长度二分，这里是对 k 值二分。
我们要求第 k 小的元素，找每个数组的从前往后第 k/2 个元素，分别为 nums1[k/2] 和 nums2[k/2]，如果 nums1[k/2] <= nums2[k/2] 则 nums1[0...k/2] 肯定不可能是第 k 小元素，将 nums1[k/2] 及其前面的元素排除，这里排除了 k/2 个元素，则继续从剩余子数组中寻找第 k-k/2 小的元素。
为什么 如果 nums1[k/2] <= nums2[k/2] 则 nums1[0...k/2] 肯定不可能是第 k 小元素？
nums1[k/2] 前面有 0… k/2-1 共 k/2-1 个元素， nums2[k/2] 前面也有 k/2-1 个元素
如果 nums1[k/2] <= nums2[k/2] ，则 nums1[0…k/2-1] 肯定比 nums1[k/2] 小，nums2[0…k/2-1] 是否比 nums1[k/2] 小我们不知道，但我们可以假设也都比 nums1[k/2] 小，所以比 nums1[k/2] 小的元素个数最多是 (k/2-1)*2 = k-2 个，也就是说 nums1[k/2] 最大也只可能是从前往后数的第 k-1 小元素，他肯定不可能是第 k 小元素，所以可以排除 nums1[k/2] 以及 nums1 中在他之前的元素。
举个具体的例子
nums1 = 1, 20, 30, 40, 50
nums2 = 2, 22, 32, 42, 52, 62
一共 11 个元素，中位数就是第 11/2+1=6 小的元素，比较两个数组中第 6/2=3 个元素，也就是 30 和 32，有 30 小于 32，也就是 nums1[k/2] <= nums2[k/2]，这里的例子就是 nums1[k/2] 最大的情况，也就是比 nums1[k/2] 小的元素个数最多的情况，可以看到 1, 20, 2, 22 都比 30 小，但即使在这种情况下 30 也只能是第 5 小元素，也就是第 k-1 小元素，不可能是第 k 小（也就是第 6 小）元素。
可以用递归实现找两个有序数组的第k小元素，但具体写起来还是有些难度的，可能要 debug 多调试几次，因为有好多边界情况，比如：
1、nums1 和 nums2 中第 k/2 个元素可能越界，此时只需用越界数组的最后一个元素代替做比较即可。
2、搜索过程中，其中一个数组可能搜索完毕了，也就是所有元素都被排除了，此时直接返回剩余数组中第 k 个元素即可，递归结束。
3、k = 1 时递归结束，直接比较两个子数组首元素返回较小者即可。
时间复杂度 O(logk) 由于 k = (m+n) / 2，所以时间复杂度也就是 O(log(m+n))
空间复杂度 O(1)
// 转化为求两个有序数组的第k小元素，二分搜索法解决
public static class SolutionV202005BinarySearch {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 两个有序数组的中位数即第 k 小的数(m+n 是偶数时需要求第 k-1 小和第 k 小的数)
int k = (nums1.length + nums2.length) / 2 + 1;
if ((nums1.length + nums2.length) % 2 == 1) {
return getKthLeastElement(nums1, nums2, 0, 0, k);
} else {
int preKthLeast = getKthLeastElement(nums1, nums2, 0, 0, k - 1); // 第 k-1 小的元素
int kthLeast = getKthLeastElement(nums1, nums2, 0, 0, k); // 第 k 小的元素
return (preKthLeast + kthLeast) / 2.0;
}
}
// 返回升序数组 nums1[nums1Start:] 和 nums2[nums2Start:] 中第 k 小的元素
public int getKthLeastElement(int [] nums1, int [] nums2, int nums1Start, int nums2Start, int k) {
// nums1 和 nums2 其中之一已结束，直接返回另一个数组的第 k 个元素
if (nums1Start >= nums1.length || nums2Start >= nums2.length) {
return nums1Start >= nums1.length ? nums2[nums2Start + k - 1] : nums1[nums1Start + k - 1];
}
if (k == 1) {
return Math.min(nums1[nums1Start], nums2[nums2Start]);
}
int mid = k / 2;
int nums1Value = nums1Start + mid - 1 < nums1.length ? nums1[nums1Start + mid - 1] : nums1[nums1.length - 1];
int nums2Value = nums2Start + mid - 1 < nums2.length ? nums2[nums2Start + mid - 1] : nums2[nums2.length - 1];
if (nums1Value <= nums2Value) {
// 排除的元素个数
int excludeCount = nums1Start + mid - 1 < nums1.length ? mid : nums1.length - nums1Start;
// 从剩余子数组中找第 k - excludeCount 小的元素
return getKthLeastElement(nums1, nums2, nums1Start + mid, nums2Start, k - excludeCount);
} else {
// 排除的元素个数
int excludeCount = nums2Start + mid - 1 < nums2.length ? mid : nums2.length - nums2Start;
// 从剩余子数组中找第 k - excludeCount 小的元素
return getKthLeastElement(nums1, nums2, nums1Start, nums2Start + mid, k - excludeCount);
}
}
}
【分步详解】两个有序数组中的中位数和Top K问题
http://blog.csdn.net/hk2291976/article/details/51107778求两个有序数组的中位数或者第k小元素
https://www.cnblogs.com/TenosDoIt/p/3554479.html[Leetcode] Median of Two Sorted Arrays 有序数组中位数
https://segmentfault.com/a/1190000002988010
GitHub代码
algorithms/leetcode/leetcode/_004_MedianOfTwoSortedArrays.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_004_MedianOfTwoSortedArrays.java
页面信息
location:protocol: host: hostname: origin: pathname: href: document:referrer: navigator:platform: userAgent: