題目:
4. 尋找兩個有序數(shù)組的中位數(shù)
解法:
解法一:
最簡單的辦法就是合并兩個有序數(shù)組, 因為數(shù)組有序, 所以很容易合并起來, 時間復(fù)雜度O(m+n);
然后取中位數(shù)即可.
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1 != null ? nums1.length : 0;
int len2 = nums2 != null ? nums2.length : 0;
// 假設(shè)合并后的數(shù)組的長度
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++];
}
// 合并后的數(shù)組求 中位數(shù)
double midNum = 0.0;
if (len % 2 == 0) {
// 偶數(shù)
int mid = len / 2 - 1;
midNum = (arr[mid] + arr[mid + 1]) / 2.0;
} else {
// 奇數(shù)
int mid = len / 2;
midNum = (double) (arr[mid]);
}
return midNum;
}
但是, 并不符合題目要求的時間復(fù)雜度 O(log(m + n)).
解法二:
見官方解答
