4. Median of Two Sorted Arrays
1. Description
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)).
2. Example
Example 1
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
3. Constraints
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10$^6$ <= nums1[i], nums2[i] <= 10$^6$
4. Solutions
Binary Search
m = i_nums1.size(), n = i_nums2.size()
Time complexity: O(logmin(m, n))
Space complexity: O(1)
class Solution {
public:
double findMedianSortedArrays(const vector<int> &nums1, const vector<int> &nums2) {
const int m = nums1.size(), n = nums2.size();
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
int left = 0, right = m, median1 = 0, median2 = 0;
while (left <= right) {
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
int nums1_left = (i == 0 ? numeric_limits<int>::min() : nums1[i - 1]);
int nums1_right = (i == m ? numeric_limits<int>::max() : nums1[i]);
int nums2_left = (j == 0 ? numeric_limits<int>::min() : nums2[j - 1]);
int nums2_right = (j == n ? numeric_limits<int>::max() : nums2[j]);
if (nums1_left <= nums2_right) {
median1 = max(nums1_left, nums2_left);
median2 = min(nums1_right, nums2_right);
left = i + 1;
} else {
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
};