Force buckle question 1 force buckle question 2, same as question 1 cow guest question
Train of thought
The data currently obtained from the data stream is divided into two parts using two heaps. The two parts differ by at most 1. One part goes into A big top heap A, and the other part goes into A small top heap B. When adding numbers from the data stream to the heap, ensure that all numbers in A are less than or equal to those in B. See method func (this *MedianFinder) AddNum(num int) for details. So it’s easy to calculate the median.
Buckle below to the output of the answer to the question (has been submitted). The solution of the problem can be slightly modified on this basis.
type MedianFinder struct {
maxHeap *MaxHeap
minHeap *MinHeap
}
/** initialize your data structure here. */
func Constructor(a) MedianFinder {
return MedianFinder{
maxHeap: NewMaxHeap(),
minHeap: NewMinHeap(),
}
}
func (this *MedianFinder) AddNum(num int) {
if this.maxHeap.IsEmpty() { // Put it in the big top heap first
this.maxHeap.Push(num)
} else if num <= this.maxHeap.Top() { // Put it in the big top heap first
this.maxHeap.Push(num)
} else {
this.minHeap.Push(num)
}
total := this.maxHeap.Len() + this.minHeap.Len()
half := total/2
// total&1 == 0, total is even, and each heap has exactly half of the data.
// total&1 ! = 0, total&1 is 1, total is odd,
// Make the number of data in the large top heap 1 more than the number in the small top heap to simplify the logic of getting the median (see the function FindMedian).
if this.maxHeap.Len() > half+total&1 { // If the number is too large, adjust it
this.minHeap.Push(this.maxHeap.Top())
this.maxHeap.Pop()
}
if this.minHeap.Len() > half { // If the number is too large, adjust it
this.maxHeap.Push(this.minHeap.Top())
this.minHeap.Pop()
}
}
func (this *MedianFinder) FindMedian(a) float64 {
// The amount of data in both heaps is the same
if this.maxHeap.Len() == this.minHeap.Len() {
return (float64(this.maxHeap.Top())+float64(this.minHeap.Top()))/2
}
// Select the top of the heap directly from the top of the heap
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 parts of the big and small top heaps to implement Heap
type Heap struct {
data []int
size int
// Whether the parent and child nodes are in positive order.
// true- "true".
// Depending on the characteristics of the big top heap/small top heap.
isParentAndChildOrdered func(parentVal, childVal int) bool
// Determine whether to select the "right" sibling (with a larger index value) when comparing sibling nodes.
// true- Select the "right" node.
// Depending on the characteristics of the big 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(a) int {
return o.size
}
func (o *Heap) IsEmpty(a) bool {
return o.size == 0
}
func (o *Heap) Top(a) 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(a) {
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(a) {
if o.IsEmpty() {
panic("Heap is empty")
}
o.data[0] = o.data[o.size- 1]
o.size--
o.siftDown()
}
func (o *Heap) siftDown(a) {
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
}
/ / big heap
type MaxHeap struct {
*Heap
}
func NewMaxHeap(a) *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
}
/ / small cap pile
type MinHeap struct {
*Heap
}
func NewMinHeap(a) *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 the codeTwo heaps, holding all the data we know, order n, order n, order n. Func (this *MedianFinder) AddNum(num int), time complexity O(logn)O(logn)O(logn). Func (this *MedianFinder) FindMedian() float64, time complexity O(1)O(1)O(1)
The code above is “embed (inheritance)+ function pointer”, the implementation below is “embed (composition)+ interface” (submitted for approval).
type MedianFinder struct {
maxHeap *Heap
minHeap *Heap
}
/** initialize your data structure here. */
func Constructor(a) MedianFinder {
return MedianFinder{
maxHeap: NewHeap(&MaxHeapCompare{}),
minHeap: NewHeap(&MinHeapCompare{}),
}
}
func (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
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(a) 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(a) int {
return o.size
}
func (o *Heap) IsEmpty(a) bool {
return o.size == 0
}
func (o *Heap) Top(a) 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(a) {
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(a) {
if o.IsEmpty() {
panic("Heap is empty")
}
o.data[0] = o.data[o.size- 1]
o.size--
o.siftDown()
}
func (o *Heap) siftDown(a) {
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 the code