No matter what everyone in the world says, I think my feelings are right. No matter what other people think, I never break my rhythm. Like things naturally can insist, do not like how also can not long.

LeetCode: the original address

Topic request

The median is the number in the middle of an ordered list. If the list length is even, the median is the average of the middle two numbers.

For example,

The median of [2,3,4] is 3

The median of [2,3] is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

Void addNum(int num) – Adds an integer from the data stream to the data structure. Double findMedian() – Returns the current median for all elements.

Example 1:

AddNum (1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2Copy the code

Advanced:

How would you optimize your algorithm if all the integers in your data stream were in the range 0 to 100? How would you optimize your algorithm if 99% of the integers in your data stream were in the range 0 to 100?

Train of thought

This problem requires two heaps, the big top heap maintains the first half of the data, the small top heap maintains the second half of the data; If the number of data is n, and if n is even, the big top heap and the small top heap maintain the same number; If n is odd, the number of large top heaps is 1 more than the number of small top heaps; When inserting new data, judge the size of it and the top of the big heap. If it is smaller than the top element, insert the big heap; otherwise, insert the small top heap. After insertion, if the number of two heaps does not meet the requirement, the heaptop element is deleted from the excessive heap for heapsizing, and the heaptop element is inserted into the bottom of the other heap for heapsizing.

code

/** * initialize your data structure here. */ var MedianFinder = function () { this.maxHeap = new Heap() this.minHeap = new Heap() } /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function (num) { let maxSize = this.maxHeap.getSize() let minSize = this.minHeap.getSize() if (maxSize === 0) { this.maxHeap.insert(num, false) } else { if (this.maxHeap.getTop() > num) { this.maxHeap.insert(num, false) } else { this.minHeap.insert(num, True)} maxSize = this.maxheap.getsize () minSize = this.minheap.getsize () if (minSize > maxSize) {// The top element needs to be removed from the small top heap, Let top = this.minheap. pop(true) this.maxheap. insert(top, False)} else if (maxSize - 1 > minSize) {// Delete the top element from the big top heap, Let top = this.maxheap. pop(false) this.minheap. insert(top, true) } } } /** * @return {number} */ MedianFinder.prototype.findMedian = function () { let maxSize = this.maxHeap.getSize() let minSize = this.minHeap.getSize() if (maxSize === minSize) { return (this.maxHeap.getTop() + this.minHeap.getTop()) / 2 } else { return this.maxHeap.getTop() } } class Heap { constructor() { this.data = [0] this.count = 0 } getTop() { return this.data[1] } pop(minFlag) { let top = this.data[1] if (this.count > 1) { this.data[1] = this.data[this.count] this.data.splice(this.count, 1) this.count-- let i = 1 if (minFlag) { while (true) { let maxPos = i if ( i * 2 <= this.count && this.data[i] > this.data[i * 2] ) { maxPos = i * 2 } if ( i * 2 + 1 <= this.count && this.data[maxPos] > this.data[i * 2 + 1] ) { maxPos = i * 2 + 1 } if (i === maxPos) { break } this.swap(i, maxPos) i = maxPos } } else { while (true) { let maxPos = i if ( i * 2 <= this.count && this.data[i] < this.data[i * 2] ) { maxPos = i * 2 } if ( i * 2 + 1 <= this.count && this.data[maxPos] < this.data[i * 2 + 1] ) { maxPos = i * 2 + 1 } if (i === maxPos) { break } this.swap(i, maxPos) i = maxPos } } } else { this.data.splice(this.count, 1) this.count-- } return top } insert(val, minFlag) { this.count++ this.data[this.count] = val let i = this.count if (minFlag) { while ( parseInt(i / 2) > 0 && this.data[i] < this.data[parseInt(i / 2)] ) { this.swap(i, parseInt(i / 2)) i = parseInt(i / 2) } } else { while ( parseInt(i / 2) > 0 && this.data[i] > this.data[parseInt(i / 2)]  ) { this.swap(i, parseInt(i / 2)) i = parseInt(i / 2) } } } getSize() { return this.count } swap(i, j) { let temp = this.data[i] this.data[i] = this.data[j] this.data[j] = temp } } /** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */Copy the code