怎么建个人网页,广州网站建设优化公司,陕西省建设执业注册中心网站,wordpress标签归类295. 数据流的中位数#xff08;困难#xff09;
题目描述#xff1a; 中位数是有序列表中间的数。如果列表长度是偶数#xff0c;中位数则是中间两个数的平均值。 例如#xff0c; [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 3) / 2 2.5
设计一个支持以下两种操作的数…295. 数据流的中位数困难
题目描述 中位数是有序列表中间的数。如果列表长度是偶数中位数则是中间两个数的平均值。 例如 [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 3) / 2 2.5
设计一个支持以下两种操作的数据结构 void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。
考察重点利用sort.IntSlice完成数组的排序并实现小顶堆继承IntSlice完成数组的逆序并实现大顶堆 大小顶堆配合查询中位数声明大顶堆存放较小的一半元素堆顶存放上半区最大元素小顶堆存放较大的一半元素堆顶存放下半区最小元素中位数即是二者均值或大顶堆堆顶元素。 go实现大小顶堆
package DataStructureimport (sort
)//真小顶堆
type MinHeap struct {sort.IntSlice
}func NewMinHeap() *MinHeap {return MinHeap{IntSlice: sort.IntSlice{}}
}func (h *MinHeap) Push(a interface{}) {h.IntSlice append(h.IntSlice, a.(int))
}func (h *MinHeap) Pop() interface{} {a : h.IntSlicev : a[len(a)-1]h.IntSlice a[:len(a)-1]return v
}type ReverseIntSlice []intfunc (x ReverseIntSlice) Len() int { return len(x) }
func (x ReverseIntSlice) Less(i, j int) bool { return x[i] x[j] }
func (x ReverseIntSlice) Swap(i, j int) { x[i], x[j] x[j], x[i] }type MaxHeap struct {ReverseIntSlice
}func NewMaxHeap() *MaxHeap {return MaxHeap{ReverseIntSlice: ReverseIntSlice{}}
}func (h *MaxHeap) Push(a interface{}) {h.ReverseIntSlice append(h.ReverseIntSlice, a.(int))
}func (h *MaxHeap) Pop() interface{} {a : h.ReverseIntSlicev : a[len(a)-1]h.ReverseIntSlice a[:len(a)-1]return v
}//这只是一个用sort方法仿制的堆耗时仍然等于对一个数组进行排序
type Heap struct {HeapItem sort.IntSlice
}func NewHeap() (h *Heap) {return Heap{HeapItem: sort.IntSlice{}}
}func (h *Heap) Push(a int) {h.HeapItem append(h.HeapItem, a)sort.Sort(h.HeapItem)
}func (h *Heap) Pop() int {temp : h.HeapItem[0]h.HeapItem h.HeapItem[1:]return temp
}实现中位数查找
package leetcodeProjectimport (container/heapd DataStructure
)type MedianFinder struct {MaxItem *d.MaxHeap //声明一个大顶堆一个小顶堆 大顶堆用来存放前一半比较小的数小顶堆用来存放后一半比较大的数即小顶堆堆顶大于大顶堆堆顶MinItem *d.MinHeap
}func Constructor6() MedianFinder {return MedianFinder{MaxItem: d.NewMaxHeap(), MinItem: d.NewMinHeap()}
}/**先将新元素加入大顶堆再将大顶堆堆顶元素最大值加入小顶堆始终保证大顶堆元素小顶堆元素||小顶堆元素1否则将小顶堆堆顶最小值加入大顶堆比如 3,4,1,23 3加入大堆 3加入小堆 “小堆多于大堆” 3加入大堆 小 大34 4加入大堆 4加入小堆 “小堆等于大堆” 小4 大31 1加入大堆 3加入小堆 “小堆多于大堆” 3加入大堆 小4 大1 32 2加入大堆 3加入小堆 “小堆等于大堆” 小4 3 大1 2
*/
func (h *MedianFinder) AddNum(num int) {heap.Push(h.MaxItem, num)heap.Push(h.MinItem, heap.Pop(h.MaxItem).(int))if h.MaxItem.Len() h.MinItem.Len() {heap.Push(h.MaxItem, heap.Pop(h.MinItem).(int))}
}func (h *MedianFinder) FindMedian() float64 {if h.MaxItem.Len() h.MinItem.Len() {return float64(h.MaxItem.ReverseIntSlice[0]h.MinItem.IntSlice[0]) / 2}return float64(h.MaxItem.ReverseIntSlice[0])
}
