Time: Read the answer

Since it is a pile exercise, it must be closer to the idea of pile

Since we only want the median, there is no need to sort all the numbers.

You can use two heaps, a maximum heap and a minimum heap

When the total number is odd (i.e., the number of maximum heaps - minimum heaps = 1), get the maximum value of the maximum heap

When the total number is an even number (i.e. the number of maximum heaps = minimum heap), get the maximum value of the maximum heap and the minimum value of the minimum heap

const swap = function (arr,i,j) {
    [arr[i],arr[j]] = [arr[j],arr[i]]
}
class Heap {
    constructor() {
        this.count = 0        this.data = new Array(this.count + 1)
    }
    shiftUp(k) {
        // Put the new elements up while(k>=1) {
            let father = Math.floor(k / 2)
            if (this.data[k] > this.data[father]) {
                swap(this.data,k,father)
                k = father
            } else {
                break            }
        }
    }
    shiftDown(k) {
        while( k * 2  <= this.count) { // Indicates that k has children let j = k
            if (k * 2 + 1 <= this.count && this.data[k * 2 + 1] > this.data[k] && this.data[k * 2 + 1] > this.data[k * 2]) {
                j = k * 2 + 1            } else if (this.data[k * 2] > this.data[k]) {
                j = k * 2            } else {
                break            }
            swap(this.data,j,k)
            k = j
        }
    }
    size() {
        return this.count    }
    isEmpty() {
        return this.count === 0    }
    insert(item) {
        this.data[++this.count] = item
        this.shiftUp(this.count)
    }
    extractMax() {
        if (this.count <= 0) return
        let ret = this.data[1]
        swap(this.data,1,this.count--)
        this.shiftDown(1)
        return ret
    }
}
var MedianFinder = function() {
    this.maxHeap = new Heap();    this.minHeap = new Heap();};MedianFinder.prototype.addNum = function(num) {
    //[1] []    // [1,2] [] -> [1] [2]    // [1,3] [2] -> [1,2] [3]    // [1,2,4] [3] -> [1,2] [3,4]    // [1,2,5] [3,4] -> [1,2,4] [4,5]    var maxHeapsize = this.maxHeap.size()
    var minHeapsize = this.minHeap.size()
    this.maxHeap.insert(num)
    var max = this.maxHeap.extractMax()
    this.minHeap.insert(-max )
    if (maxHeapsize === minHeapsize) {
        var min = Math.abs(this.minHeap.extractMax())
        this.maxHeap.insert(min)
    }
};MedianFinder.prototype.findMedian = function() {
    if (this.maxHeap.size() === this.minHeap.size()) {
        var max = this.maxHeap.extractMax()
        var min = Math.abs(this.minHeap.extractMax())
        return (max + min) / 2    } else {
        return this.maxHeap.extractMax()
    }
};

Points to note

  1. To ensure that the number of items in the max heap minus the number of items in the min heap is 0 to 1, and that the maximum value in the max heap is less than the minimum value in the min heap, each item is first entered into the max heap, which then passes the maximum value to the min heap. The number of items in the max heap is then used to determine whether to pass the minimum value of the min heap to the max heap.
  2. Only the max heap is implemented, but negative numbers can be used to create a min heap. Don’t forget to include negative numbers when exiting.