Golang中位数

题目

Golang 实现,给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例1

nums1 = [1, 3] nums2 = [2] 则中位数是 2.0

示例2

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)) }

程序运行后,控制台输出如下:

04_golang寻找中位数.png

输入了两组测试用例,得出了正确答案。