Description
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)).
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Solution
-
遍歷計數(shù)法
雙指針遍歷計數(shù)，注意m+n為奇偶的區(qū)別，時間復(fù)雜度O(m+n)误甚，不滿足題目要求蜗字，但也能AC
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
int i = 0, j = 0, median1 = 0, median2 = 0;
int countNum = 0;
while (i < m || j < n) {
int A = (i<m?nums1[i]:INT_MAX);
int B = (j<n?nums2[j]:INT_MAX);
int smaller = (A<B?A:B);
if (A < B) {
i++;
} else {
j++;
}
countNum++;
if (countNum == (m + n)/2) {
median1 = smaller;
} else if (countNum == (m + n)/2 + 1) {
median2 = smaller;
break;
}
}
return (m + n)%2 == 0 ? (median1 + median2)/2.0 : median2;
}
-
二分法
題目要求時間復(fù)雜度O(log(m+n))，考慮到數(shù)組有序尾抑，很自然需要借助二分法
