感觉维护一个数组,用折半插入来保持有序,也可以。
时间复杂度
O(logn)
python 代码
class Solution:
def __init__(self):
self.series = []
self.length = 0
def insert(self, num):
"""
:type num: int
:rtype: void
"""
self.series.append(num)
self.length += 1
self.sort1()
def sort1(self):
# 给最后一个排序,折半查找吧。
l, r = 0, self.length - 2
pivot = self.series[-1]
while l <= r:
m = int((l + r) / 2)
if self.series[m] > pivot:
r = m - 1
else:
l = m + 1
k = self.length - 2
while k > r:
self.series[k + 1] = self.series[k]
k -= 1
self.series[k + 1] = pivot
def getMedian(self):
"""
:rtype: float
"""
l = int((self.length - 1) / 2)
if self.length % 2 == 1:
return self.series[l]
else:
return (self.series[l] + self.series[l + 1])/2.0