滑动窗口的中位数-大小堆解法

对于滑动窗口，需要求出每一次的中位数，最简单暴力的方法就是对每一次的窗口内排序然后求中位数，此方法最简单。另外一种解法就是：将滑动窗口看成数据流（剑指offer上有这个题目），采用大小堆的方式来存在数据流，不过指定平衡策略要小心，各种情况都得考虑到。 简写说法：左堆=大根堆 ； 右堆=小根堆

非平衡情况：

len(左堆) = len(右堆)+2:将左堆的最大值移到右堆len(左堆) = len(右堆)-1:将右堆的最小值移到左堆len(左堆)<len(右堆)+1:不做调整len(左堆) or len(右堆)==0 :不做调整len(左堆) == len(右堆) or len(左堆) == len(右堆)+1:则需要判断左右的最小值最大值是否合理,即左堆最大值是小于等于右堆最小值

主要弄清楚非平衡情况,然后设置平衡策略将左右堆进行不断调整 来达到整个窗口的有序.

另外还需注意点: 因为窗口时固定大小,所以每一次右移,需要删除一个数,然后再添加一个数.

其他的就比较正常了,主要就是注意上述几点. 代码如下:

class WindowsMidByHeap: def __init__(self, k: int = 0, ItemType=int): self.BigHeap = [] self.SmallHeap = [] self.ItemType = ItemType self.MAXSIZE = k def __len__(self): return len(self.BigHeap) + len(self.SmallHeap) def len(self): return self.__len__() def CheckType(self, n): # 检查n的类型 if isinstance(n, self.ItemType): return True else: return False def add(self, n, remove): # 向堆中添加一个元素，并移除一个元素 if not self.CheckType(n): print("item's type must be {}".format(self.ItemType)) return False if len(self.BigHeap) == 0 or self.len() < self.MAXSIZE: heapq.heappush(self.BigHeap, -1 * n) self.__blance() return True self.__remove(remove) heapq.heappush(self.BigHeap, -1 * n) self.__blance() return True def __blance(self): # 平衡左右堆，保持大小根堆（右堆）的大小 + 1 <= 大根堆（左堆）的而大小 if len(self.BigHeap) == len(self.SmallHeap) - 1: temp = heapq.heappop(self.SmallHeap) heapq.heappush(self.BigHeap,-1 * temp) if len(self.BigHeap) == len(self.SmallHeap) + 2: temp = -1 * heapq.heappop(self.BigHeap) heapq.heappush(self.SmallHeap, temp) return # 平衡左右堆 if len(self.BigHeap) < len(self.SmallHeap) + 1: return flag = len(self.BigHeap) == 0 or len(self.SmallHeap) == 0 if flag: return len_flag = len(self.BigHeap) == len(self.SmallHeap) + 1 or len(self.BigHeap) == len(self.SmallHeap) if len_flag: Big_0 = -1 * self.BigHeap[0] Small_0 = self.SmallHeap[0] if Big_0 > Small_0: heapq.heappushpop(self.BigHeap, -1 * Small_0) heapq.heappushpop(self.SmallHeap, Big_0) return def __remove(self, n): # 从两个堆中移除元素 n if n is None: return if -1 * n in self.BigHeap: self.BigHeap.remove(-1 * n) heapq.heapify(self.BigHeap) elif n in self.SmallHeap: self.SmallHeap.remove(n) heapq.heapify(self.SmallHeap) else: return False self.__blance() return True def MidNum(self): # 去两个堆的中位数 if self.len() < self.MAXSIZE: return None n1 = None n2 = None if len(self.BigHeap) == len(self.SmallHeap): n1 = self.SmallHeap[0] / 2.0 n2 = -1 * self.BigHeap[0] / 2.0 if len(self.BigHeap) == len(self.SmallHeap) + 1: n1 = -1 * self.BigHeap[0] n2 = 0 return n1 + n2 class Solution(): def medianSlidingWindow(self, nums: list, k: int) -> list: result = [] wh = WindowsMidByHeap(k, int) for i, n in enumerate(nums): if len(wh) < k: wh.add(n, None) else: wh.add(n, nums[i - k]) re = wh.MidNum() if re is not None: result.append(re) return result