4. Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
bool needNext = !((n + m) & 1);
int move = !needNext ? (n + m) / 2 : (n + m) / 2 - 1;
double div = needNext ? 2.0 : 1.0;
int l1 = 0, l2 = 0, r1 = n-1, r2 = m-1;
while(l1 + l2 != move) {
if(l1 != n and l2 != m) {
if(nums1[l1] > nums2[l2]) l2++;
else l1++;
} else if(l1 == n) l2++;
else if(l2 == m) l1++;
}
if(l1 == n) {
double sum = nums2[l2] * 1.0;
if(needNext) sum += nums2[l2 + 1];
return sum / div;
} else if(l2 == m) {
double sum = nums1[l1] * 1.0;
if(needNext) sum += nums1[l1 + 1];
return sum / div;
} else {
double sum = min(nums1[l1], nums2[l2]);
if(!needNext) {}
else if(nums1[l1] > nums2[l2]) {
l2 += 1;
if(l2 == m) sum += nums1[l1];
else sum += min(nums1[l1], nums2[l2]);
} else {
l1 += 1;
if(l1 == n) sum += nums2[l2];
else sum += min(nums1[l1], nums2[l2]);
}
return sum / div;
}
}
};
|
