题目:
4. 寻找两个有序数组的中位数
解法:
解法一:
最简单的办法就是合并两个有序数组, 因为数组有序, 所以很容易合并起来, 时间复杂度O(m+n);
然后取中位数即可.
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1 != null ? nums1.length : 0;
int len2 = nums2 != null ? nums2.length : 0;
// 假设合并后的数组的长度
int len = len1 + len2;
int[] arr = new int[len];
int index = 0;
int i1 = 0;
int i2 = 0;
while (i1 < len1 && i2 < len2) {
arr[index++] = nums1[i1] < nums2[i2] ? nums1[i1++] : nums2[i2++];
}
while (i1 < len1) {
arr[index++] = nums1[i1++];
}
while (i2 < len2) {
arr[index++] = nums2[i2++];
}
// 合并后的数组求 中位数
double midNum = 0.0;
if (len % 2 == 0) {
// 偶数
int mid = len / 2 - 1;
midNum = (arr[mid] + arr[mid + 1]) / 2.0;
} else {
// 奇数
int mid = len / 2;
midNum = (double) (arr[mid]);
}
return midNum;
}
但是, 并不符合题目要求的时间复杂度 O(log(m + n)).
解法二:
见官方解答
