“This is the 16th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Leetcode -295 The median of the data stream

Subject to introduce

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.

The sample

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2
Copy the code

Advanced:

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

Their thinking

Solution one: sort directly

The problem solving code

var MedianFinder = function() {
    this.arr = []
};

MedianFinder.prototype.addNum = function(num) {
    this.arr.push(num)
    this.arr.sort((a, b) = > a - b)
};

MedianFinder.prototype.findMedian = function() {
    if (this.arr.length % 2= = =1) return this.arr[Math.floor(this.arr.length / 2)]
    return (this.arr[this.arr.length / 2] + this.arr[this.arr.length / 2 - 1) /2
};
Copy the code

After inserting a value each time, we simply insert it into the appropriate position. It would be too expensive to sort through the entire array each time, so we can use another method that does not require sorting all the numbers each time

Solution two: big top pile + small top pile

If we use big heap before save half of the data, using the small cap pile after save half of the data, and keep big pile top and the top of the heap size is equal or differ 1, the median will be at the top of the two heap heap element, in either of the two elements of pile top and half, or is one of the pile top elements, and we only need in the process of inserting elements, Always maintain the structure of the two heaps and ensure that the size difference between the two heaps is less than or equal to 1

Steps to solve the problem:

  1. Write aHeapClass that supports the generation of a large or small top heap based on the passed parameters. The heap containssize(heap size),top(returns the value of the heap top),pushInsert a value,pop(popup heap top value),sortBack(Adjust the structure of the heap upward),sortFront(Adjust the structure of the heap downward)
  2. Create a big top heap to hold the smaller values in the first half, and create a small top heap to hold the larger values in the second half, always keeping the size of the big top heap equal to or smaller than the size of the small top heap1
  3. If the new value is smaller than the top element of the big top heap, the new value is inserted into the big top heap. After the insertion, if the size of the big top heap is greater than the size of the small top heap, the big top heap keeps popping the top value into the small top heap until the size of the big top heap is no larger than the size of the small top heap
  4. If the new value is larger than the heaptop element of the small top heap, the new value is inserted into the small top heap, after which ifSize of small top heap - Size of large top heapIs greater than1, the small top heap keeps popping the top value of the heap into the big top heap untilSize of small top heap - Size of large top heapLess than or equal to1
  5. If two heaps are equal in size, the median is half the sum of the top elements of the two heaps; If the sizes of the two heaps are not equal, the median is the heaptop element of the small top heap

The problem solving code

var MedianFinder = function() {
    // Create a big top heap to hold the smaller values in the first half
    this.frontHeap = new Heap(1)
    // Create a small top heap to hold the larger values in the second half
    this.backHeap = new Heap(-1)}; MedianFinder.prototype.addNum =function(num) {
    // The top element of the heap can be determined only if the big top heap is not empty
    // If the new value is greater than the top element of the big top heap, it is inserted into the big top heap
    if (this.frontHeap.size() && num < this.frontHeap.top()) {
        this.frontHeap.push(num)
        // Adjust the size relationship between the two heaps
        while (this.frontHeap.size() > this.backHeap.size()) {
            this.backHeap.push(this.frontHeap.pop())
        }
    } else {
    // If the big top heap is empty or the new value is greater than the top element of the big top heap, insert into the small top heap
        this.backHeap.push(num)
        // Adjust the size relationship between the two heaps
        while (this.backHeap.size() - this.frontHeap.size() > 1) {
            this.frontHeap.push(this.backHeap.pop())
        }
    }
};

MedianFinder.prototype.findMedian = function() {
    // If two heaps are of equal size, the median is the average of the sum of the top elements of the two heaps
    if (this.frontHeap.size() === this.backHeap.size()) return (this.frontHeap.top() + this.backHeap.top()) / 2
    // If the two heaps are not of equal size, the median is the heaptop element of the small top heap
    return this.backHeap.top()
};

class Heap {
    constructor(type) {
        this.arr = []
        // Generate a small top heap according to the value of type: -1 small top heap 1 big top heap
        this.type = type
    }

    // Return the heap size
    size() {
        return this.arr.length
    }

    // Return the top of the heap element
    top() {
        return this.arr[0]}// Insert elements into the heap
    push(val) {
        this.arr.push(val)
        this.sortBack()
    }

    // Pop up the top of the heap element
    pop() {
        const val = this.arr[0]
        const back = this.arr.pop()
        if (this.size()) {
            this.arr[0] = back
            this.sortFront()
        }
        return val
    }

    // Adjust the heap structure upward
    sortBack() {
        let i = this.size() - 1
        if (this.type === -1) {
            while (i > 0 && this.arr[i] < this.arr[Math.floor((i - 1) / 2)]) {[this.arr[i], this.arr[Math.floor((i - 1) / 2)]] = [this.arr[Math.floor((i - 1) / 2)].this.arr[i]]
                i = Math.floor((i - 1) / 2)}}else {
            while (i > 0 && this.arr[i] > this.arr[Math.floor((i - 1) / 2)]) {[this.arr[i], this.arr[Math.floor((i - 1) / 2)]] = [this.arr[Math.floor((i - 1) / 2)].this.arr[i]]
                i = Math.floor((i - 1) / 2)}}}// Adjust the heap structure downward
    sortFront() {
        let i = 0
        if (this.type === -1) {
            while (i * 2 + 1 < this.size()) {
                let temp = i
                if (this.arr[temp] > this.arr[i * 2 + 1]) temp = i * 2 + 1
                if (i * 2 + 2 < this.size() && this.arr[temp] > this.arr[i * 2 + 2]) temp = i * 2 + 2
                if (temp === i) break
                [this.arr[temp], this.arr[i]] = [this.arr[i], this.arr[temp]]
                i = temp
            }
        } else {
            while (i * 2 + 1 < this.size()) {
                let temp = i
                if (this.arr[temp] < this.arr[i * 2 + 1]) temp = i * 2 + 1
                if (i * 2 + 2 < this.size() && this.arr[temp] < this.arr[i * 2 + 2]) temp = i * 2 + 2
                if (temp === i) break
                [this.arr[temp], this.arr[i]] = [this.arr[i], this.arr[temp]]
                i = temp
            }
        }
    }
}
Copy the code