首先来看一下题目:
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.
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 == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
题目的意思是:有两个有序数组nums1、nums2长度分别是m、n,求他们的中位数。时间复杂度要求为O(log (m n))。
方法一:
一个显而易见的方法总是存在的,不管它有多笨。暴力一点,直接merge以后求中位数。
package main
import "fmt"
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m := merge(nums1, nums2)
if (len(nums1) len(nums2))%2 != 0 {
return float64(m[(len(nums1) len(nums2) 1)/2-1])
}
return float64((m[(len(nums1) len(nums2))/2-1] m[(len(nums1) len(nums2))/2])) / 2
}
func merge(a, b []int) []int {
result := []int{}
i, j := 0, 0
for i < len(a) && j < len(b) {
if a[i] <= b[j] {
result = append(result, a[i])
i
} else {
result = append(result, b[j])
j
}
}
for ; i < len(a); i {
result = append(result, a[i])
}
for ; j < len(b); j {
result = append(result, b[j])
}
return result
}
func main() {
fmt.Println(findMedianSortedArrays([]int{}, []int{1, 2}))
}
但是时间复杂度为O(m n),不满足要求。
方法二:
仍然是merge的思想,但是我们不一一merge,而是二分merge,这样时间复杂度就会降到log级别。
如上图所示,整体中位数长度不会超过长度len(nums1 nums2)/2 1,所以如果在nums1中存在一个位置i,那么nums2会存在一个位置j为len(nums1 nums2)/2 1-(i 1)-1。
我们知道nums1是有序的,所以一定有nums1[i]<=nums1[i 1]且nums2[j]<=nums2[j 1]。如果再满足nums1[i]<=nums2[j 1]且nums2[j]<=nums1[i 1]的话,则可以确定整体的中位数必然存在于nums1[0:i 1]和nums2[0:j 1]中,这样就求出了整体的中位数。
图中还可见,我们把nums1放在上面,这样的话时间复杂度就是O(min(log m, log n)),比题目中要求的更快。下面看一下代码:
package main
import "fmt"
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
left, right := nums1, nums2
if len(nums1) > len(nums2) {
left, right = nums2, nums1
}
i := findIndexOfLeft(left, right, 0, len(left)-1)
sumLen := len(left) len(right)
if sumLen%2 == 0 {
if i == -1 {
return float64(right[sumLen/2-1] right[sumLen/2]) / 2
}
x, y := 0, 0
j := sumLen/2 1 - (i 1) - 1
if left[i] > right[j] {
y = left[i]
if i-1 >= 0 {
if left[i-1] > right[j] {
x = left[i-1]
} else {
x = right[j]
}
} else {
x = right[j]
}
} else {
y = right[j]
if j-1 >= 0 {
if right[j-1] > left[i] {
x = right[j-1]
} else {
x = left[i]
}
} else {
x = left[i]
}
}
return float64(x y) / 2
} else {
if i == -1 {
return float64(right[sumLen/2])
}
j := sumLen/2 1 - (i 1) - 1
if left[i] > right[j] {
return float64(left[i])
}
return float64(right[j])
}
}
func findIndexOfLeft(left, right []int, i, j int) int {
if i <= j {
leftMid := i (j-i)/2
rightMid := (len(left) len(right))/2 1 - (i (j-i)/2 1) - 1
if leftMid 1 >= len(left) {
if rightMid 1 >= len(right) || left[leftMid] <= right[rightMid 1] {
return leftMid
}
j = leftMid - 1
return findIndexOfLeft(left, right, i, j)
}
if rightMid 1 >= len(right) {
if right[rightMid] <= left[leftMid 1] {
return leftMid
}
i = leftMid 1
return findIndexOfLeft(left, right, i, j)
}
if left[leftMid] <= right[rightMid 1] && right[rightMid] <= left[leftMid 1] {
return leftMid
}
if left[leftMid] > right[rightMid 1] {
j = leftMid - 1
return findIndexOfLeft(left, right, i, j)
}
if right[rightMid] > left[leftMid 1] {
i = leftMid 1
return findIndexOfLeft(left, right, i, j)
}
}
return -1
}
func main() {
fmt.Println(findMedianSortedArrays([]int{4, 6, 7}, []int{1, 2, 3}))
}