Median of Two Sorted Arrays - LeetCode 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)).
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.
- code
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2): # make sure nums1 smaller, maybe empty.
nums1, nums2 = nums2, nums1
istart, iend = 0, len(nums1)
while istart <= iend:
i = istart + (iend - istart) // 2
j = (len(nums1) + len(nums2) + 1) // 2 - i
ileft = nums1[i - 1] if i != 0 else -inf
iright = nums1[i] if i != len(nums1) else inf
jleft = nums2[j - 1] if j != 0 else -inf # nums2[0] always valid, can't be empty as reversed at first
jright = nums2[j] if j != len(nums2) else inf
if ileft > jright:
iend = i - 1
elif jleft > iright:
istart = i + 1
else:
if (len(nums1) + len(nums2)) % 2 == 0:
return (max(ileft, jleft) + min(iright, jright)) / 2
else:
return max(ileft, jleft)
return -1
- code
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
// make sure m <= n
if (m > n) return findMedianSortedArrays(B, A);
int imin = 0, imax = m;
while (imin <= imax) {
int i = imin + (imax - imin) / 2;
int j = (m + n + 1) / 2 - i;
int A_left = i == 0 ? Integer.MIN_VALUE : A[i - 1];
int A_right = i == m ? Integer.MAX_VALUE : A[i];
int B_left = j == 0 ? Integer.MIN_VALUE : B[j - 1];
int B_right = j == n ? Integer.MAX_VALUE : B[j];
if (A_left > B_right) {
imax = i - 1;
} else if (B_left > A_right) {
imin = i + 1;
} else {
int max_left = A_left > B_left ? A_left : B_left;
int min_right = A_right > B_right ? B_right : A_right;
if ((m + n) % 2 == 1)
return max_left; // # of left_part = # of right_part + 1;
else
return (max_left + min_right) / 2.0;
}
}
return -1;
}
- code doesn’t fit O(log(m+n))
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums2) > len(nums1):
nums1, nums2 = nums2, nums1
for v in nums2:
p = bisect.bisect_left(nums1, v)
if p == len(nums1):
nums1.append(v)
else:
nums1.insert(p, v)
if len(nums1) % 2 == 0:
return (nums1[len(nums1)//2 - 1] + nums1[len(nums1)//2])/2
else:
return nums1[len(nums1)//2]