Adobe
Amazon
Apple
Bloomberg
ByteDance
Goldman Sachs
Microsoft
Uber
Wish
2021-01-23
4. Median of Two Sorted Arrays
Question:
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
Follow up: The overall run time complexity should be O(log (m+n)).
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
Solution:
Every recursion, we can eliminate 1/4 of the array that guarantee not having our target value. Need to consider the conversion between kth and index.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null && nums2 == null) {
return 0.0;
}
int left = nums1.length, right = nums2.length;
if ((left + right) % 2 == 1) {
return findKth(nums1, 0, nums2, 0, (left + right) / 2 + 1);
} else {
return (findKth(nums1, 0, nums2, 0, (left + right) / 2) + findKth(nums1, 0, nums2, 0, (left + right) / 2 + 1)) / 2.0;
}
}
// Target is kth
private int findKth(int[] nums1, int start1, int[] nums2, int start2, int target) {
if (start1 >= nums1.length) {
return nums2[start2 + target - 1];
}
if (start2 >= nums2.length) {
return nums1[start1 + target - 1];
}
if (target == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
int half = Math.min(target / 2, Math.min(nums1.length - start1, nums2.length - start2));
if (nums1[start1 + half - 1] < nums2[start2 + half - 1]) {
return findKth(nums1, start1 + half, nums2, start2, target - half);
} else {
return findKth(nums1, start1, nums2, start2 + half, target - half);
}
}
}