0004. 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.
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.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = []
Output: 2.00000
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
Follow up: The overall run time complexity should be O(log (m+n)).
Analysis¶
Finding median is basically finding the (m + n) // 2th elements for the two sorted arrays. We can use binary search to find this element.
We will use recursion to implement the binary search: int findKth(vector<int>& nums1, vector<int>& nums2, int i, int j, int k). i is the iterator pointing at nums1, and j is the iterator pointing at nums2, and k is the current k-th element we are interested in starting from nums[i] and nums[j] (note that both i, j, k are varibles, and they will change in each iteration).
Now we consider what we do for each iteration. If we have reach to the end of nums1, which mean i == nums1.size(), then we will give up nums1 and simply return the k-th element from nums2. In constrast, if we have reach to the end of nums2, which mean j == nums2.size(), then we will give up nums2 and simply return the k-th element from nums1. Don't forget there is another base case: k == 1, which means there is only one element we are interested in, and we should return the smaller one from nums1[i] and nums2[j].
Then we will eagerly grow our poiners as far as possible, and we decide to grow half the size of k. If both i + k/2 - 1 and j + k/2 - 1 are in the range, then we determine the smaller one. Since we are determining the k-th largest element, if we can be sure that all the elements from i to i + k are smaller than j to j + k (assume nums1[i + k/2 - 1] < nums2[j + k/2 - 1]), then we can safely discard all the elements from i to i + k/2 (they will be used as a "placeholder" or 炮灰 in Chinese for i to i + k/2). This logic can apply to the case when nums1[i + k/2 - 1] >= nums2[j + k/2 - 1] as well.
- Time: O(\log_2{m + n})
- Space: O(1)
Code¶
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
return (findKth(nums1, nums2, 0, 0, (m + n + 1) >> 1) + findKth(nums1, nums2, 0, 0, (m + n + 2) >> 1)) / 2.0;
}
int findKth(vector<int>& nums1, vector<int>& nums2, int i, int j, int k) {
if (i >= nums1.size()) return nums2[j + k - 1];
if (j >= nums2.size()) return nums1[i + k - 1];
if (k == 1) return min(nums1[i], nums2[j]);
int minVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX;
int minVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;
if (minVal1 < minVal2) return findKth(nums1, nums2, i + k / 2, j, k - k / 2);
else return findKth(nums1, nums2, i, j + k / 2, k - k / 2);
}
};