leetcode.480. 滑动窗口中位数(sliding-window-median)

淩亂°似流年 2022-10-27 12:10 5阅读 0赞

### 文章目录 ###

*  480. 滑动窗口中位数
 *   *  方法一：双优先队列 + 延迟删除
     *   *  Solution 类
         *  DualHeap 类

# 480. 滑动窗口中位数 #

参考[leetcode.295. 数据流的中位数][leetcode.295.]

## 方法一：双优先队列 + 延迟删除 ##

### Solution 类 ###

class Solution { 
        public double[] medianSlidingWindow(int[] nums, int k) { 
            DualHeap dh = new DualHeap(k);
            for (int i = 0; i < k; ++i) { 
                dh.insert(nums[i]);
            }
            double[] ans = new double[nums.length - k + 1];
            ans[0] = dh.getMedian();
            for (int i = k; i < nums.length; ++i) { 
                dh.insert(nums[i]);
                dh.erase(nums[i - k]);
                ans[i - k + 1] = dh.getMedian();
            }
            return ans;
        }
    
    	 class DualHeap { 
    	    //...代码放在下面 
    	 }
     
    }

### DualHeap 类 ###

class DualHeap { 
            // 大根堆，维护较小的一半元素
            private PriorityQueue<Integer> small;
            // 小根堆，维护较大的一半元素
            private PriorityQueue<Integer> large;
            // 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
            private Map<Integer, Integer> delayed;
    
            private int k;
            // small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素
            private int smallSize, largeSize;
    
            public DualHeap(int k) { 
                this.small = new PriorityQueue<Integer>(new Comparator<Integer>() { 
                    public int compare(Integer num1, Integer num2) { 
                        return num2.compareTo(num1);
                    }
                });
                this.large = new PriorityQueue<Integer>(new Comparator<Integer>() { 
                    public int compare(Integer num1, Integer num2) { 
                        return num1.compareTo(num2);
                    }
                });
                this.delayed = new HashMap<Integer, Integer>();
                this.k = k;
                this.smallSize = 0;
                this.largeSize = 0;
            }
    
            public double getMedian() { 
                return (k & 1) == 1 ? small.peek() : ((double) small.peek() + large.peek()) / 2;
            }
    
            public void insert(int num) { 
                if (small.isEmpty() || num <= small.peek()) { 
                    small.offer(num);
                    ++smallSize;
                } else { 
                    large.offer(num);
                    ++largeSize;
                }
                makeBalance();
            }
    
            public void erase(int num) { 
                delayed.put(num, delayed.getOrDefault(num, 0) + 1);
                if (num <= small.peek()) { 
                    --smallSize;
                    if (num == small.peek()) { 
                        prune(small);
                    }
                } else { 
                    --largeSize;
                    if (num == large.peek()) { 
                        prune(large);
                    }
                }
                makeBalance();
            }
    
            // 不断地弹出 heap 的堆顶元素，并且更新哈希表
            private void prune(PriorityQueue<Integer> heap) { 
                while (!heap.isEmpty()) { 
                    int num = heap.peek();
                    if (delayed.containsKey(num)) { 
                        delayed.put(num, delayed.get(num) - 1);
                        if (delayed.get(num) == 0) { 
                            delayed.remove(num);
                        }
                        heap.poll();
                    } else { 
                        break;
                    }
                }
            }
    
            // 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
            private void makeBalance() { 
                if (smallSize > largeSize + 1) { 
                    // small 比 large 元素多 2 个
                    large.offer(small.poll());
                    --smallSize;
                    ++largeSize;
                    // small 堆顶元素被移除，需要进行 prune
                    prune(small);
                } else if (smallSize < largeSize) { 
                    // large 比 small 元素多 1 个
                    small.offer(large.poll());
                    ++smallSize;
                    --largeSize;
                    // large 堆顶元素被移除，需要进行 prune
                    prune(large);
                }
            }
        }

[leetcode.295.]: https://blog.csdn.net/e891377/article/details/113621981