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; } } };
|