博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode Golang 4. 寻找两个有序数组的中位数
阅读量:5230 次
发布时间:2019-06-14

本文共 1770 字,大约阅读时间需要 5 分钟。

 

 

 

很明显我偷了懒, 没有给出正确的算法,因为官方的解法需要时间仔细看一下。。。 

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {	// 追加 -> 排序 -> 求中值	nums1 = append(nums1, nums2...)	if len(nums1) == 0 {		return 0.0	}	// 排序	sort.Ints(nums1)	//fmt.Println(nums1)	// 求中值,偶数个求中间均值, 奇数个取中间	if len(nums1)%2 == 0{		return float64(nums1[len(nums1)/2]+nums1[len(nums1)/2-1])/2	} else {		return float64(nums1[len(nums1)/2])	}}

  

这里有 LeetCode 上大神给出的符合要求的解答:

执行时间 28ms, 大神解答:

// O(log(m + n))算法,假设第k个元素是中位数,则在nums1和nums2的混合集合中找到第k个元素// 在nums1和nums2中各拿出k/2个元素,比较各自中最大的一个,这样每比较一次就会找到k/2个比k小的元素// 此时在剩下的集合中查找第k/2个元素,以此类推,当k为0时就找到了中位数(但是k不会为0,只会是1,所以当k为1时比较两个序列中首元素小的那个)// 当某个序列中所有元素都比第k个元素小时,就返回另一个队列中的第k个元素func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {	len := len(nums2) + len(nums1)	k := len / 2	if len % 2 == 0 {		return (helper(nums1, 0, nums2, 0, k + 1) + helper(nums1, 0, nums2, 0, k)) / 2.0	} else {		return helper(nums1, 0, nums2, 0, k + 1)	}}/** 依据上面的算法查找中位数* n,m分别记录nums1和nums2在哪个位置之前的数据已被筛选*/func helper(nums1 []int, n int, nums2 []int, m int, k int) float64{	if n >= len(nums1){		return float64(nums2[m + k - 1])	} else if m >= len(nums2) {		return float64(nums1[n + k - 1])	}	if k == 1{		a := math.Min(float64(nums1[n]), float64(nums2[m]))		return a	}	p1 := n + k/2 - 1	p2 := m + k - k/2 - 1	var mid1, mid2 int	if p1 >= len(nums1) {		mid2 = nums2[p2]		mid1 = mid2 + 1	} else if p2 >= len(nums2) {		mid1 = nums1[p1]		mid2 = mid1 + 1	} else {		mid1 = nums1[p1]		mid2 = nums2[p2]	}	if mid1 < mid2 {		k = k - (p1 + 1 - n)		if k == 0{			return float64(mid2)		}		return helper(nums1, p1+1, nums2, m, k)	} else {		k = k - (p2 + 1 - m)		if k == 0{			return float64(mid1)		}		return helper(nums1, n, nums2, p2+1, k)	}}

   LeetCode 深似海。。。

转载于:https://www.cnblogs.com/gettolive/p/10178492.html

你可能感兴趣的文章