[B] [C] [D]

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

The sort order

One of the simplest and most straightforward ways to do this is to maintain an array, store all the numbers and when you need to get the median, sort the array and then get the median based on the odd and even number of elements in the array

The code is as follows:

var MedianFinder = function() { this.arr = []; }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { this.arr.push(num); }; / * * * @ return {number} * / MedianFinder prototype. FindMedian = function () {/ / an array sort this. Arr. Sort (a, b) = > (a - b) / / Const len = this.arr. Length; if(len%2) return this.arr[len>>1] return (this.arr[(len>>1)-1]+this.arr[len>>1])/2 };Copy the code

This method of commit can pass, but it is inefficient because the array is sorted every time

Binary insert

To avoid sorting the array every time, we can insert the new integer directly into the appropriate place in the array so that the array is always sorted, so that we don’t have to sort it every time we get the median

The code is as follows:

Var MedianFinder = function() {this.arr = []; }; / * * * @ param {number} num * @ return void * / MedianFinder. Attach the prototype. AddNum = function (num) {/ / every time insert the num to orderly array suitable location, Maintain orderly array if (this. Arr. Length = = 0 | | num < = this. Arr [0]) this. Arr. Unshift (num) else if (num > = this. Arr [this. Arr. Length - 1)) this.arr.push(num) else{ let l = 0,r = this.arr.length-1; while(l<r){ const mid = (l+r)>>1; if(this.arr[mid]<num) l = mid+1 else r = mid } this.arr.splice(l,0,num) } }; / * * * @ return {number} * / MedianFinder prototype. FindMedian = function () {/ / according to the length of the array parity return the corresponding median const len = this.arr.length; if(len%2) return this.arr[len>>1] return (this.arr[(len>>1)-1]+this.arr[len>>1])/2 };Copy the code

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 animation is shown below:

The code is as follows:

Constructor (compare){this.arr = []; this.size = 0; This.arr. Push (val){this.arr. Push (val); this.size++; If (this.size>1){let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&this.compare(this.arr[parent],this.arr[cur])){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; } // pop(){const res = this.arr[0]; this.arr[0] = this.arr.pop(); this.size--; // let cur = 0, childl = 1,childr = 2; while( (childl<this.size&&this.compare(this.arr[cur],this.arr[childl])) || (childr<this.size&&this.compare(this.arr[cur],this.arr[childr])) ){ if(childr<this.size&&this.compare(this.arr[childl],this.arr[childr])){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]]  cur = childl } childl = cur*2+1,childr = cur*2+2; } return res; Top (){return this.arr[0]}} var MedianFinder = function() { This.bigheap = new Heap((a,b) => a<b) this.littleHeap = new Heap((a,b) => a>b)}; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { // When both heaps are empty or the current value is less than or equal to the top element of the large top heap, Insert big pile jacking the if (this. BigHeap. Size = = = 0 | | num < = this. BigHeap. Top ()) {this. BigHeap. Push (num) / / if big top pile element quantity is greater than the number of + 1 / / small cap pile elements If (this.bigheap.size > this.littleheap.size +1){this.littleheap.push (this.bigheap.pop ())}}else{this.littleheap.push (this.bigheap.pop ())}else{ If (this.littleheap.size > this.bigheap.size){this.littleheap.push (num) {if(this.littleheap.size > this.bigheap.size){ this.bigHeap.push(this.littleHeap.pop()) } } }; / * * * @ return {number} * / MedianFinder prototype. FindMedian = function () {/ / if equal number two pile element, If (this.bigheap.size === this.littleheap.size){return (this.bigheap.top ()+ this.littleheap.top ())/2} // Return this.bigheap.top (); };Copy the code

Here we have leetcode- Interview question 17.20- Continuous median

If you have any questions or suggestions, please leave a comment!