题解 | #数据流中的中位数#
数据流中的中位数
https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1
# -*- coding:utf-8 -*- class Solution: record=[] record_min=[] # dagen record_max=[] # xiaogen def Insert(self, num): self.record.append(num ) # 形成一个小跟堆 # 每次先往min里面放一个 self.record_min.append(num) for i in range(len(self.record_min),-1,-1): self.makeheap_min(i) # 插入之后,把最大的弹过去 tmp=self.record_min[0] self.record_min[0]=self.record_min[-1] self.record_min.pop(-1) self.makeheap_min(0) self.record_max.insert(-1,tmp) for i in range(len(self.record_max),-1,-1): self.makeheap_max(i) # 如果min比max少一个,就把max中最小的弹回来 if len(self.record_min)-len(self.record_max)<0: tmp=self.record_max[0] self.record_max[0]=self.record_max[-1] self.record_max.pop(-1) self.makeheap_max(0) self.record_min.insert(-1,tmp) for i in range(len(self.record_min),-1,-1): self.makeheap_min(i) # write code here def GetMedian(self): # write code here if len(self.record)%2==0: # oushu return (self.record_max[0]+self.record_min[0])/2 else: return self.record_min[0] def makeheap_max(self,idx): # xiaogen maxNode=len(self.record_max)-1 l=2*idx+1 r=2*idx+2 if l>maxNode: return elif r>maxNode: if self.record_max[idx]>self.record_max[l]: # 互换位置 tmp=self.record_max[idx] self.record_max[idx]=self.record_max[l] self.record_max[l]=tmp self.makeheap_max(l) else: if self.record_max[l]<=self.record_max[r]: if self.record_max[l]>self.record_max[idx]: return else: tmp=self.record_max[idx] self.record_max[idx]=self.record_max[l] self.record_max[l]=tmp self.makeheap_max(l) else: if self.record_max[r]>self.record_max[idx]: return else: tmp=self.record_max[idx] self.record_max[idx]=self.record_max[r] self.record_max[r]=tmp self.makeheap_max(r) def makeheap_min(self,idx): # dagen maxNode=len(self.record_min)-1 l=2*idx+1 r=2*idx+2 if l>maxNode: return elif r>maxNode: if self.record_min[idx]<=self.record_min[l]: # 互换位置 tmp=self.record_min[idx] self.record_min[idx]=self.record_min[l] self.record_min[l]=tmp self.makeheap_min(l) else: if self.record_min[l]>=self.record_min[r]: if self.record_min[l]<self.record_min[idx]: return else: tmp=self.record_min[idx] self.record_min[idx]=self.record_min[l] self.record_min[l]=tmp self.makeheap_min(l) else: if self.record_min[r]<=self.record_min[idx]: return else: tmp=self.record_min[idx] self.record_min[idx]=self.record_min[r] self.record_min[r]=tmp self.makeheap_min(r)