package main import ( "fmt" ) /*** 295. 数据流的中位数 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如: [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构: void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。 示例: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 进阶: 如果数据流中所有整数都在 0 到 100 范围内,你将如何优化你的算法? 如果数据流中 99% 的整数都在 0 到 100 范围内,你将如何优化你的算法? */ func main() { finder := Constructor() finder.AddNum(-1) fmt.Println(finder.Nums, "=>", finder.FindMedian()) finder.AddNum(-2) fmt.Println(finder.Nums, "=>", finder.FindMedian()) finder.AddNum(-3) fmt.Println(finder.Nums, "=>", finder.FindMedian()) finder.AddNum(-4) fmt.Println(finder.Nums, "=>", finder.FindMedian()) finder.AddNum(-5) fmt.Println(finder.Nums, "=>", finder.FindMedian()) finder.AddNum(-6) fmt.Println(finder.Nums, "=>", finder.FindMedian()) } type MedianFinder struct { Nums []int } /** initialize your data structure here. */ func Constructor() MedianFinder { return MedianFinder{[]int{}} } func (this *MedianFinder) AddNum(num int) { index := BinaryQuery(this.Nums, num) if index == -1 { var i []int i = append(i, num) this.Nums = append(i, this.Nums...) } else { // ⚠️注意:存在元素替换问题,在设置 a 时,因为内存存储是连续的,会导致将 b 的值覆盖掉 // a, b := this.Nums[:index], this.Nums[index:] // this.Nums = append(append(a, num), b...) // 避免重复,将数组复制 a, b := make([]int, index), make([]int, len(this.Nums)-index) copy(a, this.Nums[:index]) copy(b, this.Nums[index:]) this.Nums = append(append(a, num), b...) } } func (this *MedianFinder) FindMedian() float64 { i := len(this.Nums) ii := i / 2 if i%2 == 0 { return float64(this.Nums[ii]+this.Nums[ii-1]) / 2 } return float64(this.Nums[ii]) } /** * Your MedianFinder object will be instantiated and called as such: * obj := Constructor(); * obj.AddNum(num); * param_2 := obj.FindMedian(); */ // BinaryQuery 使用二分查找 对顺序列表进行定位范围,未定位导未知,返回-1 func BinaryQuery(list []int, target int) int { // 定义并初始化low和high,声明mid low, high := 0, len(list) if high == 0 { return -1 } high -= 1 // 具体下标 lowVal, highVal := list[0], list[high] if target <= lowVal { return 0 } if target >= highVal { return high + 1 } // 使用二分查找 对顺序列表进行定位范围,未定位导未知,返回-1 for low <= high { mid := (low + high) / 2 if high == low { return low } else if list[mid] > target { high = mid - 1 } else if list[mid] < target { low = mid + 1 } else { return mid } } return -1 }