用 Golang 实现,给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
package main
import (
"fmt"
)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
if len(nums2) == 0 {
findMedianSortedArrays(nums2, nums1)
}
if len(nums1) == 0 {
if len(nums2)%2 == 0 {
return float64(nums2[len(nums2)/2-1] + nums2[len(nums2)/2]) / 2
} else {
return float64(nums2[len(nums2)/2])
}
}
indexA, indexB := 0, 0
var preArray []int
for i := 0; i <= (len(nums1)+len(nums2))/2; i++ {
if indexA >= len(nums1) && indexB < len(nums2) {
preArray = append(preArray, nums2[indexB])
indexB++
}
if indexA < len(nums1) && indexB >= len(nums2) {
preArray = append(preArray, nums1[indexA])
indexA++
}
if indexA < len(nums1) && indexB < len(nums2) && nums1[indexA] <= nums2[indexB] {
preArray = append(preArray, nums1[indexA])
indexA++
} else if indexA < len(nums1) && indexB < len(nums2) && nums1[indexA] > nums2[indexB] {
preArray = append(preArray, nums2[indexB])
indexB++
}
}
if (len(nums1)+len(nums2))%2 == 0 {
return float64(preArray[len(preArray)-1]+preArray[len(preArray)-2]) / 2
} else {
return float64(preArray[len(preArray)-1])
}
}
func main() {
fmt.Println("嗨客网(www.haicoder.net)")
var num1 = []int{1, 3}
var num2 = []int{2}
var num3 = []int{1, 2}
var num4 = []int{3, 4}
fmt.Println(findMedianSortedArrays(num1, num2))
fmt.Println(findMedianSortedArrays(num3, num4))
}
程序运行后,控制台输出如下:
输入了两组测试用例,得出了正确答案。