官方题解还有个“延迟删除”优化“元素移出窗口”的操作
太多了还没看 (调通“两个优先队列”已经让我筋疲力尽)
关于两个优先队列(堆)取数据流的中位数 还有一个比较基础的题板295. 数据流的中位数
Java的自定义比较器Comparator
要用包装类的compareTo()
!!!!
Java的自定义比较器Comparator
要用包装类的compareTo()
!!!!
Java的自定义比较器Comparator
要用包装类的compareTo()
!!!!
为什么?-2 - Integer.MAX_VALUE
和1 - Integer.MIN_VALUE
就直接溢出了
鬼知道我调了大半钟头数据 才发现是比较器的问题 (而且半个月前就被这个坑过 不长记性)
正题 给一个数组和滑动窗口长度 求“从左至右所有窗口”的中位数组成的结果数组
窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
怎么做呢 从基础的版本来 我们先不考虑窗口的事 求一下整个数字流的中位数
数字流 中位数
--------------- -----
1 1
1 3 (1+3)/2 = 2
1 3 -1 1
1 3 -1 -3 (-1+1)/2 = 0
1 3 -1 -3 5 1
1 3 -1 -3 5 3 (1+3)/2 = 2
用两个优先队列
一个大根堆存当前数组中升序排列的前一半 (堆顶是前一半的最大值)
一个小根堆存当前数组中升序排列的后一半 (堆顶是后一半的最小值)
巧了不是 中位数不就是从这两个堆顶元素里选么
当总个数为奇数时 必有一个队列比另一个多出一个元素 中位数就是这个多出来的堆顶(队首)
当总个数为偶数时 两个队列一样长 中位数就是这两个堆顶(队首)相加除以2
队列直接new就行 我们需要实现什么功能?
添加元素 接收到一个数字后,需要添加到队列里
添加到哪个队列呢?根据与当前堆顶元素的大小关系决定
- 规定当总数奇数时 后一半的队列比前一半多出1个 以便奇数时直接取后一半的队首
- 首先 如果两个队列都是空的 默认放到后一半里面
- 如果大于等于后一半的堆顶(也就是后一半的最小值)那么新数字必然先放入后一半 (注意这个“先”)
- 如果小于后一半的最小值,自然也就放入前一半的队列
现在来解决“先”的问题 上面只是简单的根据大小关系确定分类
但是我们规定了“当总数奇数时 后一半的队列比前一半多出1个”
即后一半的个数必然大于前一半 (实际上当总个数为偶数时相等 奇数时会且仅会多出1个)
如果原先两个队列相等 新数又刚好加入到前一半 违反规定 前一半个数大于后一半了 奇数时取后一半队首是错误的
如果原先后一半的队列已经比前一半多一个了 新数又恰好加入到后一半 也就是多出2个了 而此时总数是偶数 按照“中位数选两队首的平均数”自然有可能出错
因此添加数字后 需要进行平衡队列
即 把两队列的状态修正到 前一半个数与后一半相等或少一位
因为是一个一个数字添加的 所以需要修正的状态有两个
① 前一半比后一半多一个 此时移除前一半的队首到后一半
② 后一半比前一半多两个 此时移除后一半的队首到前一半
获取中位数、添加、平衡的操作都解决了 那么基础题也就能A了
class MedianFinder {
PriorityQueue<Integer> low, high;
/** initialize your data structure here. */
public MedianFinder() {
low = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1)); // 血的教训 包装类用compareTo 这题不用没事 下一题就爆了
high = new PriorityQueue<>();
}
public void addNum(int num) {
if (high.isEmpty() || num >= high.peek()) high.add(num); // 如果后一半没数字或者当前数字大于后一半的最小值 就放入后一半
else low.add(num); // 否则放入前一半
int cntL = low.size(), cntR = high.size(); // 获取一下前后各自队列长度
if (cntL > cntR) high.add(low.poll()); // 如果前一半偏长 最大值移入后一半
else if (cntR > cntL + 1) low.add(high.poll()); // 如果后一半偏长 最小值移入前一半
}
public double findMedian() {
if (low.size() == high.size()) // 前后两半个数相等 总数即为偶数 那么中位数在两队首取平均
return ((double) low.peek() + high.peek()) / 2;
else return high.peek(); // 否则在取后一半的队首
}
}
基础题结束 回归正题
加上了限制条件“滑动窗口” 怎么办呢
原先是直接加入新数字就行了 现在有了窗口长度的限制 新数字的加入有可能导致最旧的数字被移除
因此 要加上从队列中移除元素的操作
怎么移除呢
当目标数大于或等于后一半的队首时 它必然可以在后一半的队列里找到 因此调用后一半队列的remove()
即可
同理 当目标数小于后一半的队首时 它必然可以在前一半的队列里找到
remove()
的开销是$O(\frac k2)$的 官方题解的“延迟删除”就是用来优化这个的 不过我菜 不挑食
注意删除后也是需要平衡一次队列的
class Solution {
PriorityQueue<Integer> low = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1)); // 血的教训
PriorityQueue<Integer> high = new PriorityQueue<>();
void makeBalance() { // 平衡队列 哪边偏多了 就把队首移到另外一边
int lenL = low.size(), lenH = high.size();
if (lenL > lenH) high.add(low.poll());
else if (lenH > lenL + 1) low.add(high.poll());
}
void add(int x) { // 添加数字
if (high.isEmpty() || x >= high.peek()) high.add(x);
else low.add(x);
makeBalance();
}
void remove(int x) { // 删除数字
if (x >= high.peek()) high.remove(x);
else low.remove(x);
makeBalance();
}
double getMid(int k) { // 获取中位数 窗口长度是固定的 奇偶也是固定的
if ((k & 1) == 1) return high.peek();
else return ((double) low.peek() + high.peek()) / 2;
}
public double[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length, pos = 0;
double[] ans = new double[n - k + 1]; // 存答案 前k-1个数是不需要求中位数的 因为没凑成一个完整窗口
for (int i = k - 2; i >= 0; i--) add(nums[i]); // 先把前k-1个加入队列
for (int i = k - 1; i < n; i++) { // 从第k个开始
add(nums[i]); // 每加入一个新数
ans[pos++] = getMid(k); // 求一次中位数
remove(nums[i - k + 1]); // 再删除一次窗口最左端数字
}
return ans;
}
}