Commit936b0d4

authored

Create 295-Find-Median-from-Data-Stream.py

1 parentc7dd012 commit936b0d4Copy full SHA for 936b0d4

File tree

+30

-0

lines changed

+30

-0

lines changed

Lines changed: 30 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,30 @@`
	`1`	`+classMedianFinder:`
	`2`	`+`
	`3`	`+def__init__(self):`
	`4`	`+"""`
	`5`	`+ initialize your data structure here.`
	`6`	`+ """`
	`7`	`+# two heaps, large, small, minheap, maxheap`
	`8`	`+# heaps should be equal size`
	`9`	`+self.small,self.large= [], []# maxHeap, minHeap (python default)`
	`10`	`+`
	`11`	`+defaddNum(self,num:int)->None:`
	`12`	`+heapq.heappush(self.small,-1*num)`
	`13`	`+`
	`14`	`+if (self.smallandself.largeand (-1*self.small[0])>self.large[0]):`
	`15`	`+val=-1*heapq.heappop(self.small)`
	`16`	`+heapq.heappush(self.large,val)`
	`17`	`+`
	`18`	`+iflen(self.small)>len(self.large)+1:`
	`19`	`+val=-1*heapq.heappop(self.small)`
	`20`	`+heapq.heappush(self.large,val)`
	`21`	`+iflen(self.large)>len(self.small)+1:`
	`22`	`+val=heapq.heappop(self.large)`
	`23`	`+heapq.heappush(self.small,-1*val)`
	`24`	`+`
	`25`	`+deffindMedian(self)->float:`
	`26`	`+iflen(self.small)>len(self.large):`
	`27`	`+return-1*self.small[0]`
	`28`	`+eliflen(self.large)>len(self.small):`
	`29`	`+returnself.large[0]`
	`30`	`+return (-1*self.small[0]+self.large[0])/2`

Comments

(0)