剣指Offer(Pythonの多様な考え方の実現):データストリームの中位数
1288 ワード
剣指Offer(Pythonの多様な考え方の実現):データストリームの中位数
面接41題:
テーマ:データストリームの中央値
問題:データストリームの中位数をどのように取得しますか?データストリームから奇数個の数値を読み出すと、中位数は、すべての数値がソートされた後に中間に位置する数値である.データストリームから偶数個の数値が読み出されると、中位数は、すべての数値が並べ替えられた後の中間の2つの数の平均値となります.
問題を解く構想の1:直接法、並べ替えた後に中位数を求めます
問題を解く構想2:
面接41題:
テーマ:データストリームの中央値
問題:データストリームの中位数をどのように取得しますか?データストリームから奇数個の数値を読み出すと、中位数は、すべての数値がソートされた後に中間に位置する数値である.データストリームから偶数個の数値が読み出されると、中位数は、すべての数値が並べ替えられた後の中間の2つの数の平均値となります.
問題を解く構想の1:直接法、並べ替えた後に中位数を求めます
class Solution:
def __init__(self):
self.array=[]
def Insert(self, num):
# write code here
self.array.append(num)
self.array.sort()
def GetMedian(self,M):
# write code here
length=len(self.array)
if len(self.array)%2==1:
return self.array[length//2]
else:
return (self.array[length//2-1]+self.array[length//2])/2.0
問題を解く構想2:
import heapq as hq
class MedianFinder:
def __init__(self):
self.lo, self.hi = [], [] # lo is max_heap, hi is min_heap
def addNum(self, num):
hq.heappush(self.lo, -num)
hq.heappush(self.hi, -hq.heappop(self.lo))
if len(self.lo) < len(self.hi):
hq.heappush(self.lo, -hq.heappop(self.hi))
def findMedian(self):
if len(self.lo) == len(self.hi):
return (-self.lo[0]+self.hi[0]) / 2.0
else:
return float(-self.lo[0])