source: https://leetcode.com/problems/median-of-two-sorted-arrays/
C/C++ Solution to LeetCode problem 4. Median of Two Sorted Arrays.
Problem
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))
.
Examples
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.
Constraints
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Solution
This one was difficult, and I could figure out how to solve it without mergin the two arrays until I had the number of elements equal to the hald of the total number of elements (median: all elements sorted, take the value at the middle of the list of elements).
So, watch the next video, it gaves an excelent explanation of how to solve it, the basic idea is:
- We know the total number of elements.
- Whe know how many we need to have the first half of them.
- Both arrays are sorted, so, for example, if we have two identical arrays, we need the first half of each one.
- This algorithm performs a binary search to find how many elements of the first array we need, and how many of the second (partition points).
- Knowing those partition points, we just identify the order, and we get the median.
Algorithm explanation
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
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums2.size() < nums1.size())
return findMedianSortedArrays(nums2, nums1);
int size = nums1.size() + nums2.size();
int medianPos = size / 2;
int l = -1;
int r = nums1.size() - 1;
while (1) {
int i = (l + r) >= 0 ? (l + r) / 2: -1;
int j = medianPos - i - 2;
int l1 = i >= 0 ? nums1[i] : -INT_MAX;
int r1 = (i + 1) < nums1.size() ? nums1[i + 1] : INT_MAX;
int l2 = j >= 0 ? nums2[j] : -INT_MAX;
int r2 = (j + 1) < nums2.size() ? nums2[j + 1] : INT_MAX;
if (l1 <= r2 && l2 <= r1) {
if (size % 2 == 0)
return (double)(((long)max(l1, l2) + (long)min(r1, r2)) / (double)2.0);
return (double)min(r1, r2);
} else if (l1 > r2) {
r = i - 1;
} else {
l = i + 1;
}
}
return 0;
}
};