原題
數(shù)字是不斷進(jìn)入數(shù)組的涛菠，在每次添加一個(gè)新的數(shù)進(jìn)入數(shù)組的同時(shí)返回當(dāng)前新數(shù)組的中位數(shù)赐稽。
持續(xù)進(jìn)入數(shù)組的數(shù)的列表為：[1, 2, 3, 4, 5]，則返回[1, 1, 2, 2, 3]
持續(xù)進(jìn)入數(shù)組的數(shù)的列表為：[4, 5, 1, 3, 2, 6, 0]，則返回 [4, 4, 4, 3, 3, 3, 3]
持續(xù)進(jìn)入數(shù)組的數(shù)的列表為：[2, 20, 100]倚舀，則返回[2, 2, 20]
時(shí)間復(fù)雜度為O(nlogn)
解題思路
- Priority Queue
- 維護(hù)一個(gè)MaxHeap和一個(gè)MinHeap
- size(MinHeap) - 1 < size(MaxHeap) < size(MaxHeap)
- MaxHeap可以通過(guò)MinHeap實(shí)現(xiàn)叹哭，每次put相反數(shù)入隊(duì)
- python中Priority Queue的使用
import Queue
q = Queue.PriorityQueue()
q.put(3)
q.put(1)
q.put(2)
a = q.get()
print a # output = 1
完整代碼
import Queue
class Solution:
"""
@param nums: A list of integers.
@return: The median of numbers
"""
def medianII(self, nums):
result = []
if not nums:
return result
median = nums[0]
MaxHeap, MinHeap = Queue.PriorityQueue(), Queue.PriorityQueue()
result.append(median)
for i in range(1, len(nums)):
if nums[i] > median:
MinHeap.put(nums[i])
else:
MaxHeap.put(-nums[i])
if MaxHeap.qsize() > MinHeap.qsize():
MinHeap.put(median)
median = -MaxHeap.get()
if MaxHeap.qsize() + 1 < MinHeap.qsize():
MaxHeap.put(-median)
median = MinHeap.get()
result.append(median)
return result
