LeetCode-in-All
4. Median of Two Sorted Arrays
Hard
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.
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
Solution
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
if len(nums1) > len(nums2) {
nums1, nums2 = nums2, nums1
}
x, y := len(nums1), len(nums2)
low, high := 0, x
for low <= high {
partitionX := (low + high) / 2
partitionY := (x+y+1)/2 - partitionX
maxLeftX := getIntValue(nums1, partitionX-1)
minRightX := getIntValue(nums1, partitionX)
maxLeftY := getIntValue(nums2, partitionY-1)
minRightY := getIntValue(nums2, partitionY)
if maxLeftX <= minRightY && maxLeftY <= minRightX {
if (x+y)%2 == 0 {
return float64(max(maxLeftX, maxLeftY)+min(minRightX, minRightY)) / 2
} else {
return float64(max(maxLeftX, maxLeftY))
}
} else if maxLeftX > minRightY {
high = partitionX - 1
} else {
low = partitionX + 1
}
}
return 0.0
}
func getIntValue(nums []int, index int) int {
if index < 0 {
return -1000000
}
if index >= len(nums) {
return 1000000
}
return nums[index]
}