面试题17.20.连续中值

链接：面试题17.20.连续中值
难度：Hard
标签：设计、双指针、数据流、排序、堆（优先队列）
简介：随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。

题解 1 - typescript

• 编辑时间：2021-04-10
• 执行用时：280ms
• 内存消耗：58.9MB
• 编程语言：typescript
• 解法介绍：构建左侧大顶堆和右侧小顶堆，中间值为左侧堆最大值和右侧堆最小值的比较。

class Heap<T> {
  private arr: T[] = [];
  get isEmpty() {
    return this.size === 0;
  }
  get size() {
    return this.arr.length;
  }
  get top() {
    return this.arr[0];
  }
  constructor(private compare: (t1: T, t2: T) => number) {}
  add(num: T): void {
    this.arr.push(num);
    this.shiftUp(this.size - 1);
  }
  remove(): T {
    const num = this.arr.shift()!;
    if (this.size) {
      this.arr.unshift(this.arr.pop()!);
      this.shiftDown(0);
    }
    return num;
  }
  private shiftUp(index: number): void {
    if (index === 0) return;
    const parentIndex = (index - 1) >> 1;
    if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
      [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
      this.shiftUp(parentIndex);
    }
  }
  private shiftDown(index: number): void {
    let childrenIndex = index * 2 + 1;
    if (childrenIndex > this.size - 1) return;
    if (
      childrenIndex + 1 <= this.size - 1 &&
      this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
    ) {
      childrenIndex++;
    }
    if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
      [this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
      this.shiftDown(childrenIndex);
    }
  }
}
class MedianFinder {
  private leftHeap = new Heap<number>((num1: number, num2: number) => num1 - num2);
  private rightHeap = new Heap<number>((num1: number, num2: number) => num2 - num1);
  get size() {
    return this.leftHeap.size + this.rightHeap.size;
  }
  addNum(num: number): void {
    if (!this.leftHeap.size || this.leftHeap.top >= num) {
      this.leftHeap.add(num);
    } else {
      this.rightHeap.add(num);
    }
    if (this.leftHeap.size === this.rightHeap.size + 2) {
      this.rightHeap.add(this.leftHeap.remove());
    } else if (this.leftHeap.size === this.rightHeap.size - 1) {
      this.leftHeap.add(this.rightHeap.remove());
    }
  }
  findMedian(): number {
    if (this.size % 2 === 0) {
      return (this.leftHeap.top + this.rightHeap.top) / 2;
    } else {
      return this.leftHeap.top;
    }
  }
}