优先级队列
解题思路
大顶堆存放前半部分，小顶堆存放后半部分；
数据流为奇数时，保证两个堆的长度相差1，那么长度较大的堆的堆顶就是中位数；
数据流为偶数时，保证两个堆的长度相等，两个堆的堆顶相加除二就是中位数；
图解
复杂度
-
时间复杂度：
O(logN)- 查找中位数
O(1) - 获取堆顶元素
O(1) - 添加数字
O(logN) - 堆的插入和弹出操作
O(logN)
- 查找中位数
-
空间复杂度：
O(n)，主要为优先队列的开销；
代码实现
class MedianFinder {
maxHeap: Heap
minHeap: Heap
constructor() {
// 大顶堆 放小的那一半数字
this.maxHeap = new Heap((a, b) => a > b);
// 小顶堆 放大的那一半数字
this.minHeap = new Heap((a, b) => a < b);
}
addNum(num: number): void {
if (!this.maxHeap.size || num < this.maxHeap.peek()) {
this.maxHeap.push(num);
} else {
this.minHeap.push(num);
}
// 维护两个堆的平衡
if (this.maxHeap.size - this.minHeap.size > 1) {
this.minHeap.push(this.maxHeap.pop());
} else if (this.minHeap.size > this.maxHeap.size) {
this.maxHeap.push(this.minHeap.pop());
}
}
findMedian(): number {
if ((this.maxHeap.size + this.minHeap.size) % 2 === 0) {
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
}
return this.maxHeap.peek();
}
}
class Heap {
arr: Array<number>
compare: Function
constructor(compare) {
this.arr = [0]; // 忽略 0 这个索引,方便计算左右节点
this.compare = compare ? compare : (a, b) => a > b; // 默认是大顶堆
}
get size() {
return this.arr.length - 1;
}
// 新增元素
push(item) {
this.arr.push(item);
this.shiftUp(this.arr.length - 1);
}
// 元素上浮，k 是索引
shiftUp(k) {
let { arr, compare, parent } = this;
// 当前元素 > 父元素，则进行交换
while (k > 1 && compare(arr[k], arr[parent(k)])) {
this.swap(parent(k), k);
k = parent(k); // 更新 k 的位置为父元素的位置（交换了位置）
}
}
// 弹出堆顶
pop() {
if (this.arr.length == 1) return null;
this.swap(1, this.arr.length - 1);// 将结尾元素和堆顶元素交换位置
let head = this.arr.pop(); // 删除堆顶
this.sinkDown(1); // 再做下沉操作
return head;
}
// 元素下沉
sinkDown(k) {
let { arr, compare, left, right, size } = this;
while (left(k) <= size) {
// 1. 拿到左右节点的最大值
let child = left(k);
if (right(k) <= size && compare(arr[right(k)], arr[child])) {
child = right(k);
}
// 2. k 满足大顶堆或小顶堆，什么都不做
if (compare(arr[k], arr[child])) {
return;
}
// 3. 交换位置后，继续下沉操作
this.swap(k, child);
k = child; // 更新位置
}
}
// 获取堆顶元素
peek() {
return this.arr[1];
}
// 获取左边元素节点
left(k) {
return k * 2;
}
// 获取右边元素节点
right(k) {
return k * 2 + 1;
}
// 获取父节点
parent(k) {
return Math.floor(k >> 1);
}
// i、j 交换位置
swap(i, j) {
[this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]];
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
1855.下标对中的最大距离
上一篇
评论
