[B] [C] [D]

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

Advanced:

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

This is exactly the same as leetcode — Interview question 17.20 — Continuous median except for the advanced requirements

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

However, this solution requires sorting the array every time the median is retrieved, and this problem has a higher limitation on time complexity, so this solution is feasible, but the raising exceeds the time limit

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

And finally, a little bit about the progression requirements in this case

If the given number is an integer greater than zero, that is the most efficient way of sorting count sorted array in the process of maintenance, and maintenance of two Pointers point to the current median, if the number of array elements is an odd number Two Pointers point to the same element in the middle If the number of array elements is even, the two Pointers point to the middle two elements

If 1% of the elements are not in the 0-100 range, maintain them separately

This is also the official optimization solution, but neither the official nor other solutions have implemented the corresponding code. In the process of implementing the corresponding code, I found that maintaining two Pointers is more complicated than expected and the efficiency after submission is not high, similar to the binary insertion method, But the logic and the code are a little bit more complicated and it’s not a universal way to do it, so I’m not going to go into it

At this point we are done with Leetcode-295 – the median of the data stream

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