LeetCode刷题实战480:滑动窗口中位数
共 2686字,需浏览 6分钟
·
2021-12-28 13:44
示例
解题
import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length;
int m = n - k + 1;
// 结果的尺寸
double[] res = new double[m];
//两个堆,一个最大堆,一个最小
PriorityQueuemaxHeap = new PriorityQueue (k, Collections.reverseOrder());
PriorityQueueminHeap = new PriorityQueue (k);
for (int i = 0; iint num = nums[i];
// 让maxHeap始终保存小于一半的值,minHeap保存大于一半的,正好两半
if( maxHeap.size() == 0 || maxHeap.peek() >= num) maxHeap.add(num);
else minHeap.add(num);
// 维护两个堆,保证两个堆得大小,要么保持一致(偶数时),要么maxHeap多一个(奇数时)
if( minHeap.size() > maxHeap.size() ) maxHeap.add(minHeap.poll());
if( maxHeap.size() > minHeap.size() + 1 ) minHeap.add(maxHeap.poll());
// 如果需要输出
if ( i-k+1 >=0 ){
if( k % 2 == 1 ) res[i- k + 1] = maxHeap.peek();
else res[i- k + 1] = (maxHeap.peek()/2.0 + minHeap.peek()/2.0);
// 小心溢出
// 移除并更新
int toBeRemove = nums[i - k + 1];
if( toBeRemove <= maxHeap.peek()) maxHeap.remove(toBeRemove);
else minHeap.remove(toBeRemove);
// 维护两个堆,保证两个堆得大小,要么保持一致(偶数时),要么maxHeap多一个(奇数时)
if( minHeap.size() > maxHeap.size() ) maxHeap.add(minHeap.poll());
if( maxHeap.size() > minHeap.size() + 1 ) minHeap.add(maxHeap.poll());
}
}
return res;
}
}
LeetCode刷题实战462:最少移动次数使数组元素相等 II
LeetCode刷题实战470:用 Rand7() 实现 Rand10()