スライドウィンドウの中位数-サイズスタック解法

スライドウィンドウについては、毎回の中位数を求める必要があります.最も簡単な暴力的な方法は、毎回のウィンドウ内をソートして中位数を求めることです.この方法が最も簡単です.

のもう一つの解法は、スライドウィンドウをデータストリーム(剣指offerにこの問題がある)と見なし、サイズスタック方式でデータストリームが存在するが、バランスポリシーを指定するには注意し、様々な状況を考慮しなければならない.左堆=大根堆;右ヒープ=小根ヒープ

アンバランス:

len(左ヒープ)=len(右ヒープ)+2:左ヒープの最大値を右ヒープ

に移動

len(左ヒープ)=len(右ヒープ)-1:右ヒープの最小値を左ヒープ

に移動

len(左スタック)

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