Find Median from Data Stream
HardTwo PointersDesignSortingHeap (Priority Queue)Data Stream
Solution
import { Heap } from '@algorithm/lib';
export class MedianFinder {
small: Heap<number>;
large: Heap<number>;
constructor() {
this.small = new Heap((a, b) => a - b);
this.large = new Heap((a, b) => a - b);
}
addNum(num: number): void {
if (this.small.length === this.large.length) {
this.small.push(-num);
this.large.push(-(this.small.pop() as number));
} else {
this.large.push(num);
this.small.push(-(this.large.pop() as number));
}
}
findMedian(): number {
if (this.large.peek === undefined || this.small.peek === undefined) return 0;
if (this.small.length === this.large.length) {
return (this.large.peek - this.small.peek) / 2;
} else {
return this.large.peek;
}
}
}