Median of Two Sorted Arrays (H)
题目
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)).
You may assume nums1 and nums2 cannot be both empty.
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(log(m+n)))。
思路
常规方法合并后取中位数，复杂度为(O(m+n))。(在合并中排到指定个数时即可停止并返回输出)
复杂度为(O(log(m+n)))的方法：结合二分和递归，将问题转化为求两数组组成的集合中第k小的数。每次都比较数组A和B中第k/2小的数A[k/2-1]和B[k/2-1]，这里会有以下三种情况：
(记两数组合并后的升序数组为C)
- A[k/2-1] < B[k/2-1]，说明A[0]-A[k/2-1]这k/2个数均小于B[k/2-1]，而B[k/2-1]前有k/2-1个数也小于它，那么即使A[k/2-1]取最大，也只能在C中排到第k-1位，不可能是第k小，所以将A[0]-A[k/2-1]这k/2个数全部删去，问题转化为在剩余数组成的集合中求第k-p小的数(用p表示是因为不一定每次都能删去k/2个数，A的长度可能小于k/2，这时会把整个数组删去)。
- A[k/2-1] > B[k/2-1]，与上面的情况相似，这时删去B中的k/2个数，在剩余数组成的集合中求第k-q小的数。
- A[k/2-1] = B[k/2-1]，这时A中有k/2-1个数比A[k/2-1]小，B中也有k/2-1个数比B[k/2-1]小，共有k-2个数比这两个值小，那么在C中A[k/2-1]和B[k/2-1]正好是第k-1和k小的数(并列)，即所求的中位数就是A[k/2-1] (或B[k/2-1])。
处理完递归，来考虑边界条件，共有三种情况：
- 当一个数组中所有数都被排除后，只要在另一个数组中找到对应的第k小数即可。
- 当k=1时，只要返回两个数组第一个元素中最小的那个。
- A[k/2-1] = B[k/2-1]，已包含在递归处理中。
代码中为了方便处理，总是保持A为长度较小的数组。
代码实现
Java
class Solution {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length;
// 将奇偶两种情况统一处理
int a = findkth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, (total + 1) / 2);
int b = findkth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, (total + 2) / 2);
return 1.0 * (a + b) / 2;
}
public static int findkth(int[] A, int as, int ae, int[] B, int bs, int be, int k) {
int alen = ae - as + 1;
int blen = be - bs + 1;
// 边界条件处理
if (alen > blen) {
return findkth(B, bs, be, A, as, ae, k);
} else if (alen == 0) {
return B[k - 1];
} else if (k == 1) {
return Math.min(A[as], B[bs]);
}
// 递归处理
int p = Math.min(alen, k / 2);
int q = k - p;
if (A[as + p - 1] < B[bs + q - 1]) {
return findkth(A, as + p, ae, B, bs, be, k - p);
} else if (A[as + p - 1] > B[bs + q - 1]) {
return findkth(A, as, ae, B, bs + q, be, k - q);
} else {
return A[as + p - 1];
}
}
}
JavaScript
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
let len = nums1.length + nums2.length
let mid1 = findK(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, Math.floor((len + 1) / 2))
let mid2 = findK(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, Math.floor((len + 2) / 2))
return (mid1 + mid2) / 2
}
let findK = function (nums1, l1, r1, nums2, l2, r2, k) {
if (r1 - l1 > r2 - l2) {
return findK(nums2, l2, r2, nums1, l1, r1, k)
}
if (l1 > r1) {
return nums2[k - 1]
}
if (k === 1) {
return Math.min(nums1[l1], nums2[l2])
}
let p = Math.min(r1 - l1 + 1, Math.floor(k / 2))
let q = k - p
if (nums1[l1 + p - 1] < nums2[l2 + q - 1]) {
return findK(nums1, l1 + p, r1, nums2, l2, r2, k - p)
} else if (nums1[l1 + p - 1] > nums2[l2 + q - 1]) {
return findK(nums1, l1, r1, nums2, l2 + q, r2, k - q)
} else {
return nums1[l1 + p - 1]
}
}