leetcode 295. The median of the data stream

leetcode 295. The median of the data stream

Stay button topic 1
power button topic 2, with the same title 1
cattle off topic

Ideas

Using two heaps, the data currently obtained from the data stream is divided into two parts. The number of data in the two parts differs by at most 1. One part is placed in a large top pile A, and the other part is placed in a small top pile B. When adding the numbers in the data stream to the heap, ensure that all numbers in A are less than or equal to the numbers in B. See method for specific details

func (this *MedianFinder) AddNum(num int)
. In this way, calculating the median is simple.

The answer to the question on Likou is given below (submitted for approval). On this basis, the solution of the Niuke problem can be slightly modified.

type MedianFinder struct { maxHeap *MaxHeap minHeap *MinHeap } /** initialize your data structure here. */ func Constructor () MedianFinder { return MedianFinder{ maxHeap: NewMaxHeap(), minHeap: NewMinHeap(), } } FUNC (the this MedianFinder *) AddNum (NUM int ) { IF this.maxHeap.IsEmpty () {//stack top priority into a large this.maxHeap.Push(num) } else if num <= this.maxHeap.Top() { //Put the big top heap first this.maxHeap.Push(num) } else { this.minHeap.Push(num) } total := this.maxHeap.Len() + this.minHeap.Len() half := total/2 //When total&1 == 0, total is an even number, and each heap is divided into exactly half of the data. //When total&1 != 0, the result of total&1 is 1, and total is an odd number, //Make the number of data in the large top heap 1 more than that in the small top heap, simplifying the logic when obtaining the median (see the function FindMedian ). if this.maxHeap.Len()> half+total& 1 { //adjust when the number is too large this.minHeap.Push(this.maxHeap.Top()) this.maxHeap.Pop() } if this.minHeap.Len()> half { //adjust if there are more this.maxHeap.Push(this.minHeap.Top()) this.minHeap.Pop() } } func (this *MedianFinder) FindMedian () float64 { //The amount of data in the two heaps is the same if this.maxHeap.Len() == this.minHeap.Len() { return ( float64 (this.maxHeap.Top() )+ float64 (this.minHeap.Top()))/ 2 } //If the amount of data is different, take the top of the large top heap directly return float64 (this.maxHeap.Top()) } /** * Your MedianFinder object will be instantiated and called as such: * obj := Constructor(); * obj.AddNum(num); * param_2 := obj.FindMedian(); */ //Extract the common part of the large top heap and the small top heap and implement it as Heap type Heap struct { data [] int size int //Whether the parent node and child node are in "positive order". //true-"positive sequence". //Determined by the characteristics of the large top heap/small top heap. isParentAndChildOrdered func (parentVal, childVal int ) bool //When comparing sibling nodes, determine whether to select the sibling node "to the right" (larger index value). //true-select the "right" node. //Determined by the characteristics of the large top heap/small top heap. shouldChooseRightSibling func (leftVal, rightVal int ) bool } func NewHeap (isParentAndChildOrdered func (parentVal, childVal int ) bool , shouldChooseRightSibling func (leftVal, rightVal int ) bool ) * Heap { return &Heap{ isParentAndChildOrdered: isParentAndChildOrdered, shouldChooseRightSibling: shouldChooseRightSibling, } } func (o *Heap) Len () int { return o.size } func (o *Heap) IsEmpty () bool { return o.size == 0 } func (o *Heap) Top () int { if o.IsEmpty() { panic ( "Heap is empty" ) } return o.data[ 0 ] } func (o *Heap) Push (n int ) { if o.size < len (o.data) { o.data[o.size] = n } else { o.data = append (o.data, n) } o.size++ o.siftUp() } func (o *Heap) siftUp () { if o.size < 2 { return } var ( child = o.size -1 childV = o.data[child] ) for child> 0 { p := (child -1 )>> 1 pV := o.data[p] if o.isParentAndChildOrdered(pV, childV) { break } o.data[child] = pV child = p } o.data[child] = childV } func (o *Heap) Pop () { if o.IsEmpty() { panic ( "Heap is empty" ) } o.data[ 0 ] = o.data[o.size -1 ] o.size-- o.siftDown() } func (o *Heap) siftDown () { if o.size < 2 { return } var ( p int pV = o.data[p] ) for { child := 2 *p + 1 if child >= o.size { break } if child+ 1 <o.size && o.shouldChooseRightSibling(o.data[child], o.data[child+ 1 ]) { child++ } childV := o.data[child] if o.isParentAndChildOrdered(pV, childV) { break } o.data[p] = childV p = child } o.data[p] = pV } // type MaxHeap struct { *Heap } func NewMaxHeap () * MaxHeap { o := &MaxHeap{} o.Heap = NewHeap(o.isParentAndChildOrdered, o.shouldChooseRightSibling) return o } func (MaxHeap) isParentAndChildOrdered (parentVal, childVal int ) bool { return parentVal >= childVal } func (MaxHeap) shouldChooseRightSibling (leftVal, rightVal int ) bool { return leftVal <rightVal } // type MinHeap struct { *Heap } func NewMinHeap () * MinHeap { o := &MinHeap{} o.Heap = NewHeap(o.isParentAndChildOrdered, o.shouldChooseRightSibling) return o } func (MinHeap) isParentAndChildOrdered (parentVal, childVal int ) bool { return parentVal <= childVal } func (MinHeap) shouldChooseRightSibling (leftVal, rightVal int ) bool { return leftVal> rightVal } Copy code

Two heaps, holding all known data, the space complexity isO(n)O(n) .
method

func (this *MedianFinder) AddNum(num int)
,time complexityO(logn)O(logn) .
method
func (this *MedianFinder) FindMedian() float64
,time complexityO(1)O(1) .

The above code is "embedding (inheritance) + function pointer", the following implementation is changed to "embedding (combination) + interface" (submitted for approval).

type MedianFinder struct { maxHeap *Heap minHeap *Heap } /** initialize your data structure here. */ func Constructor () MedianFinder { return MedianFinder{ maxHeap: NewHeap(&MaxHeapCompare{}), minHeap: NewHeap(&MinHeapCompare{}), } } FUNC (the this MedianFinder *) AddNum (NUM int ) { IF this.maxHeap.IsEmpty () { this.maxHeap.Push(num) } else if num <= this.maxHeap.Top() { this.maxHeap.Push(num) } else { this.minHeap.Push(num) } total := this.maxHeap.Len() + this.minHeap.Len() half := total/2 if total& 1 == 0 { //even number for this.maxHeap.Len()> half { this.minHeap.Push(this.maxHeap.Top()) this.maxHeap.Pop() } for this.minHeap.Len()> half { this.maxHeap.Push(this.minHeap.Top()) this.minHeap.Pop() } } else { oneMore := half+ 1 for this.maxHeap.Len()> oneMore { this.minHeap.Push(this.maxHeap.Top()) this.maxHeap.Pop() } for this.minHeap.Len()> half { this.maxHeap.Push(this.minHeap.Top()) this.minHeap.Pop() } } } func (this *MedianFinder) FindMedian () float64 { if this.maxHeap.Len() == this.minHeap.Len() { return ( float64 (this.maxHeap.Top())+ float64 (this.minHeap.Top( )))/ 2 } return float64 (this.maxHeap.Top()) } /** * Your MedianFinder object will be instantiated and called as such: * obj := Constructor(); * obj.AddNum(num); * param_2 := obj.FindMedian(); */ type HeapCompare interface { IsParentAndChildOrdered(parentVal, childVal int ) bool ShouldChooseRightSibling(leftVal, rightVal int ) bool } type Heap struct { data [] int size int HeapCompare } func NewHeap (cmp HeapCompare) * Heap { return &Heap{ HeapCompare: cmp, } } func (o *Heap) Len () int { return o.size } func (o *Heap) IsEmpty () bool { return o.size == 0 } func (o *Heap) Top () int { if o.IsEmpty() { panic ( "Heap is empty" ) } return o.data[ 0 ] } func (o *Heap) Push (n int ) { if o.size < len (o.data) { o.data[o.size] = n } else { o.data = append (o.data, n) } o.size++ o.siftUp() } func (o *Heap) siftUp () { if o.size < 2 { return } var ( child = o.size -1 childV = o.data[child] ) for child> 0 { p := (child -1 )>> 1 pV := o.data[p] if o.IsParentAndChildOrdered(pV, childV) { break } o.data[child] = pV child = p } o.data[child] = childV } func (o *Heap) Pop () { if o.IsEmpty() { panic ( "Heap is empty" ) } o.data[ 0 ] = o.data[o.size -1 ] o.size-- o.siftDown() } func (o *Heap) siftDown () { if o.size < 2 { return } var ( p int pV = o.data[p] ) for { child := 2 *p + 1 if child >= o.size { break } if child+ 1 <o.size && o.ShouldChooseRightSibling(o.data[child], o.data[child+ 1 ]) { child++ } childV := o.data[child] if o.IsParentAndChildOrdered(pV, childV) { break } o.data[p] = childV p = child } o.data[p] = pV } type MaxHeapCompare struct {} func (o *MaxHeapCompare) IsParentAndChildOrdered (parentVal, childVal int ) bool { return parentVal >= childVal } func (o *MaxHeapCompare) ShouldChooseRightSibling (leftVal, rightVal int ) bool { return leftVal <rightVal } type MinHeapCompare struct {} func (o *MinHeapCompare) IsParentAndChildOrdered (parentVal, childVal int ) bool { return parentVal <= childVal } func (o *MinHeapCompare) ShouldChooseRightSibling (leftVal, rightVal int ) bool { return leftVal> rightVal } Copy code