295.数据流的中位数

链接：295.数据流的中位数
难度：Hard
标签：设计、双指针、数据流、排序、堆（优先队列）
简介：中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

题解 1 - typescript

• 编辑时间：2021-04-10
• 执行用时：272ms
• 内存消耗：58.5MB
• 编程语言：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;
    }
  }
}

题解 2 - typescript

• 编辑时间：2021-08-27
• 执行用时：1648ms
• 内存消耗：68.1MB
• 编程语言：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 {
  left = new Heap<number>((t1, t2) => t1 - t2);
  right = new Heap<number>((t1, t2) => t2 - t1);
  get cnt() {
    return this.left.size + this.right.size;
  }
  addNum(num: number): void {
    if (this.left.size === 0 && this.right.size === 0) {
      this.left.add(num);
    } else if (this.left.top < num) {
      this.right.add(num);
    } else {
      this.left.add(num);
    }
    if (this.right.size + 1 > this.left.size) this.left.add(this.right.remove());
    if (this.left.size - 1 > this.right.size) this.right.add(this.left.remove());
  }
  findMedian(): number {
    return this.cnt % 2 === 0 ? (this.left.top + this.right.top) / 2 : this.left.top;
  }
}

题解 3 - c

• 编辑时间：2021-11-28
• 执行用时：376ms
• 内存消耗：83MB
• 编程语言：c
• 解法介绍：堆。

#define swap(a, b)              \
    {                           \
        __typeof(a) __temp = a; \
        a = b;                  \
        b = __temp;             \
    }
typedef struct
{
    int size, len, *data;
    int(*comp)(int, int);
} Heap;
Heap *heap_create(int len, int (*comp)(int, int))
{
    Heap *h = (Heap *)malloc(sizeof(Heap));
    h->comp = comp;
    h->len = len;
    h->size = 0;
    h->data = (int *)malloc(sizeof(int) * len);
    return h;
}
void heap_free(Heap *h)
{
    if (!h)
        return;
    free(h->data);
    free(h);
}
void heap_shift_up(Heap *h, int idx)
{
    while (idx)
    {
        int p = (idx - 1) / 2;
        if (h->comp(h->data[idx], h->data[p]) > 0)
        {
            swap(h->data[p], h->data[idx]);
            idx = p;
        }
        else
            break;
    }
}
void heap_shift_down(Heap *h, int idx)
{
    while (idx * 2 + 1 < h->size)
    {
        int child = idx;
        if (h->comp(h->data[child], h->data[idx * 2 + 1]) < 0)
        {
            child = idx * 2 + 1;
        }
        if (
            idx * 2 + 2 < h->len && h->comp(h->data[child], h->data[idx * 2 + 2]) < 0)
        {
            child = idx * 2 + 2;
        }
        if (child == idx)
            break;
        swap(h->data[idx], h->data[child]);
        idx = child;
    }
}
int heap_remove(Heap *h)
{
    if (!h || h->size == 0)
        return -1;
    int val = h->data[0];
    h->data[0] = h->data[--h->size];
    heap_shift_down(h, 0);
    return val;
}
int heap_add(Heap *h, int val)
{
    if (!h || h->len == h->size)
        return 0;
    h->data[h->size] = val;
    heap_shift_up(h, h->size++);
    return val;
}
int heap_top(Heap *h)
{
    if (!h || h->size == 0)
        return -1;
    return h->data[0];
}
void heap_show(Heap *h)
{
#ifdef DEBUG
    printf("Heap : [");
    for (int i = 0; i < h->len; i++)
    {
        if (!h->data[i])
            continue;
        i != 0 && printf(",");
        printf("%d", h->data[i]);
    }
    printf("]\n");
#endif
}
int comp1(int a, int b)
{
    return a - b;
}
int comp2(int a, int b)
{
    return b- a;
}
typedef struct {
    Heap *h1, *h2;
} MedianFinder;
#define MAX 200000
MedianFinder* medianFinderCreate() {
    MedianFinder *o = (MedianFinder *)malloc(sizeof(MedianFinder));
    o->h1 = heap_create(MAX, comp1);
    o->h2 = heap_create(MAX, comp2);
    return o;
}
void medianFinderAddNum(MedianFinder* obj, int num) {
    if(obj->h1->size == 0 || num <= heap_top(obj->h1)) {
        heap_add(obj->h1, num);
        if (obj->h1->size > obj->h2->size + 1) heap_add(obj->h2, heap_remove(obj->h1));
    }
    else {
        heap_add(obj->h2, num);
        if (obj->h2->size > obj->h1->size) heap_add(obj->h1, heap_remove(obj->h2));
    }
}
double medianFinderFindMedian(MedianFinder* obj) {
    if((obj->h1->size + obj->h2->size) & 1) return heap_top(obj->h1);
    else return (heap_top(obj->h1) + heap_top(obj->h2)) / 2.0;
}
void medianFinderFree(MedianFinder* obj) {
    heap_free(obj->h1);
    heap_free(obj->h2);
    free(obj);
}