class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
}
};
480. 滑动窗口中位数
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[2,3,4]，中位数是 3[2,3]，中位数是 (2 + 3) / 2 = 2.5给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
示例：
给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
窗口位置 中位数 --------------- ----- [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,5,6]。
提示：
k 始终有效，即：k 始终小于等于输入的非空数组的元素个数。10 ^ -5 以内的答案将被视作正确答案。相似题目
原站题解
cpp 解法, 执行用时: 108 ms, 内存消耗: 34.1 MB, 提交时间: 2023-06-13 14:29:20
class Solution {
public:
priority_queue<int> small;
priority_queue<int, vector<int>, greater<int> > big;
unordered_map<int, int> mp;
double get(int& k){
if(k%2) return small.top();
else return ((long long)small.top()+big.top())*0.5;
}
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
for(int i = 0; i < k; i++){small.push(nums[i]);};
for(int i = 0; i < k / 2; i++){big.push(small.top()); small.pop();}
vector<double> ans{get(k)};
for(int i = k; i < nums.size(); i++){
int balance = 0;
int l = nums[i-k];
mp[l]++;
if(!small.empty() && l<=small.top()){balance--;}
else {balance++;}
if(!small.empty() && nums[i] <= small.top()){
small.push(nums[i]);
balance++;
}
else{
big.push(nums[i]);
balance--;
}
if(balance>0){
big.push(small.top());
small.pop();
}
if(balance<0){
small.push(big.top());
big.pop();
}
while(!small.empty() && mp[small.top()]>0){
mp[small.top()]--;
small.pop();
}
while(!big.empty() && mp[big.top()]>0){
mp[big.top()]--;
big.pop();
}
ans.push_back(get(k));
}
return ans;
}
};
golang 解法, 执行用时: 80 ms, 内存消耗: 11.3 MB, 提交时间: 2023-06-13 14:28:53
type hp struct {
sort.IntSlice
size int
}
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func (h *hp) push(v int) { h.size++; heap.Push(h, v) }
func (h *hp) pop() int { h.size--; return heap.Pop(h).(int) }
func (h *hp) prune() {
for h.Len() > 0 {
num := h.IntSlice[0]
if h == small {
num = -num
}
if d, has := delayed[num]; has {
if d > 1 {
delayed[num]--
} else {
delete(delayed, num)
}
heap.Pop(h)
} else {
break
}
}
}
var delayed map[int]int
var small, large *hp
func medianSlidingWindow(nums []int, k int) []float64 {
delayed = map[int]int{} // 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
small = &hp{} // 大根堆，维护较小的一半元素
large = &hp{} // 小根堆，维护较大的一半元素
makeBalance := func() {
// 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
if small.size > large.size+1 { // small 比 large 元素多 2 个
large.push(-small.pop())
small.prune() // small 堆顶元素被移除，需要进行 prune
} else if small.size < large.size { // large 比 small 元素多 1 个
small.push(-large.pop())
large.prune() // large 堆顶元素被移除，需要进行 prune
}
}
insert := func(num int) {
if small.Len() == 0 || num <= -small.IntSlice[0] {
small.push(-num)
} else {
large.push(num)
}
makeBalance()
}
erase := func(num int) {
delayed[num]++
if num <= -small.IntSlice[0] {
small.size--
if num == -small.IntSlice[0] {
small.prune()
}
} else {
large.size--
if num == large.IntSlice[0] {
large.prune()
}
}
makeBalance()
}
getMedian := func() float64 {
if k&1 > 0 {
return float64(-small.IntSlice[0])
}
return float64(-small.IntSlice[0]+large.IntSlice[0]) / 2
}
for _, num := range nums[:k] {
insert(num)
}
n := len(nums)
ans := make([]float64, 1, n-k+1)
ans[0] = getMedian()
for i := k; i < n; i++ {
insert(nums[i])
erase(nums[i-k])
ans = append(ans, getMedian())
}
return ans
}
python3 解法, 执行用时: 268 ms, 内存消耗: 30.9 MB, 提交时间: 2023-06-13 14:28:37
class DualHeap:
def __init__(self, k: int):
# 大根堆，维护较小的一半元素，注意 python 没有大根堆，需要将所有元素取相反数并使用小根堆
self.small = list()
# 小根堆，维护较大的一半元素
self.large = list()
# 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
self.delayed = collections.Counter()
self.k = k
# small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素
self.smallSize = 0
self.largeSize = 0
# 不断地弹出 heap 的堆顶元素，并且更新哈希表
def prune(self, heap: List[int]):
while heap:
num = heap[0]
if heap is self.small:
num = -num
if num in self.delayed:
self.delayed[num] -= 1
if self.delayed[num] == 0:
self.delayed.pop(num)
heapq.heappop(heap)
else:
break
# 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
def makeBalance(self):
if self.smallSize > self.largeSize + 1:
# small 比 large 元素多 2 个
heapq.heappush(self.large, -self.small[0])
heapq.heappop(self.small)
self.smallSize -= 1
self.largeSize += 1
# small 堆顶元素被移除，需要进行 prune
self.prune(self.small)
elif self.smallSize < self.largeSize:
# large 比 small 元素多 1 个
heapq.heappush(self.small, -self.large[0])
heapq.heappop(self.large)
self.smallSize += 1
self.largeSize -= 1
# large 堆顶元素被移除，需要进行 prune
self.prune(self.large)
def insert(self, num: int):
if not self.small or num <= -self.small[0]:
heapq.heappush(self.small, -num)
self.smallSize += 1
else:
heapq.heappush(self.large, num)
self.largeSize += 1
self.makeBalance()
def erase(self, num: int):
self.delayed[num] += 1
if num <= -self.small[0]:
self.smallSize -= 1
if num == -self.small[0]:
self.prune(self.small)
else:
self.largeSize -= 1
if num == self.large[0]:
self.prune(self.large)
self.makeBalance()
def getMedian(self) -> float:
return float(-self.small[0]) if self.k % 2 == 1 else (-self.small[0] + self.large[0]) / 2
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
dh = DualHeap(k)
for num in nums[:k]:
dh.insert(num)
ans = [dh.getMedian()]
for i in range(k, len(nums)):
dh.insert(nums[i])
dh.erase(nums[i - k])
ans.append(dh.getMedian())
return ans
java 解法, 执行用时: 46 ms, 内存消耗: 54.1 MB, 提交时间: 2023-06-13 14:28:20
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 {
// 大根堆，维护较小的一半元素
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);
}
}
}
cpp 解法, 执行用时: 108 ms, 内存消耗: 33 MB, 提交时间: 2023-06-13 14:28:05
// 双优先队列 + 延迟删除
class DualHeap {
private:
// 大根堆，维护较小的一半元素
priority_queue<int> small;
// 小根堆，维护较大的一半元素
priority_queue<int, vector<int>, greater<int>> large;
// 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
unordered_map<int, int> delayed;
int k;
// small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素
int smallSize, largeSize;
public:
DualHeap(int _k): k(_k), smallSize(0), largeSize(0) {}
private:
// 不断地弹出 heap 的堆顶元素，并且更新哈希表
template<typename T>
void prune(T& heap) {
while (!heap.empty()) {
int num = heap.top();
if (delayed.count(num)) {
--delayed[num];
if (!delayed[num]) {
delayed.erase(num);
}
heap.pop();
}
else {
break;
}
}
}
// 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
void makeBalance() {
if (smallSize > largeSize + 1) {
// small 比 large 元素多 2 个
large.push(small.top());
small.pop();
--smallSize;
++largeSize;
// small 堆顶元素被移除，需要进行 prune
prune(small);
}
else if (smallSize < largeSize) {
// large 比 small 元素多 1 个
small.push(large.top());
large.pop();
++smallSize;
--largeSize;
// large 堆顶元素被移除，需要进行 prune
prune(large);
}
}
public:
void insert(int num) {
if (small.empty() || num <= small.top()) {
small.push(num);
++smallSize;
}
else {
large.push(num);
++largeSize;
}
makeBalance();
}
void erase(int num) {
++delayed[num];
if (num <= small.top()) {
--smallSize;
if (num == small.top()) {
prune(small);
}
}
else {
--largeSize;
if (num == large.top()) {
prune(large);
}
}
makeBalance();
}
double getMedian() {
return k & 1 ? small.top() : ((double)small.top() + large.top()) / 2;
}
};
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
DualHeap dh(k);
for (int i = 0; i < k; ++i) {
dh.insert(nums[i]);
}
vector<double> ans = {dh.getMedian()};
for (int i = k; i < nums.size(); ++i) {
dh.insert(nums[i]);
dh.erase(nums[i - k]);
ans.push_back(dh.getMedian());
}
return ans;
}
};