Topic describes

[topic address]

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() -> 2Copy the code

Analysis: the heap

So if you want to get the median, you want to maintain a maximum of the first half and a minimum of the second half, and you can do that with a heap so you can do it with a big top heap, Maintain the first half of the low value through a small top heap maintain the second half of the large value maintain the difference between the number of elements in the two heaps is not greater than 1, and the number of elements in the big top heap is greater than or equal to the number of elements in the small top heap so that when you get the median, if the two heaps have the same number of elements, The median is the average of the two top elements of the heap otherwise the median is the top element of the big top heap

The diagram is as follows:

The following code

var MedianFinder = function() { this.item = []; }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { this.item.push(num) }; / * * * @ return {number} * / MedianFinder prototype. FindMedian = function () {/ / sorting, (this.item).sort(function(a,b){return a-b}); If (this.item.length % 2 == 0){return ((this.item[this.item.length / 2] +) (this.item)[this.item.length /2 -1]) /2); }else{ return (this.item)[(this.item.length - 1)/2] } };Copy the code

Here we have leetcode- Interview question 17.20- Continuous median