17.20. Median value in a row

Random numbers are generated and passed to a method. Can you do this by looking for the median of all current values and saving it every time a new value is generated?

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:

AddNum (1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2

Analysis of the

  • Implement a maximum heap from small to large sort, implement a minimum heap from large to small sort
  • Maintain the maximum heap and minimum heap, always keep the maximum heap is 1 more than the minimum heap or equal, when the length of the maximum heap and minimum heap are equal (the last of the maximum heap + the last of the minimum heap)/2, when the length of the maximum heap is greater than the last of the maximum heap

Code implementation

/** * initialize your data structure here. */ var MedianFinder = function() { this.left = [-Infinity] this.right = [Infinity] }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { if(num <= this.left[this.left.length - 1]){ this.left.push(num) this.left = this.left.sort((a,b) => a - b) }else{ this.right.push(num) this.right = this.right.sort((a,b) => b - a) } this.resize() }; MedianFinder.prototype.resize = function(){ if(this.left.length - this.right.length >1){ this.right.push(this.left.pop()) }else if(this.right.length > this.left.length){ this.left.push(this.right.pop()) } } /** * @return {number} */ MedianFinder.prototype.findMedian = function() { if(this.left.length === this.right.length){ return (this.left[this.left.length-1] + this.right[this.right.length-1]) / 2 }else{ return this.left[this.left.length-1] }}; /** * 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