## 题目描述：

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

`[2,3,4]` , the median is `3`

`[2,3]`, the median is `(2 + 3) / 2 = 2.5`

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

For example:

```add(1)
findMedian() -> 1.5
findMedian() -> 2```

## 题目大意：

[2,3,4], 中位数是 3

[2,3], 中位数是 (2 + 3) / 2 = 2.5

• void addNum(int num) - 从数据流向数据结构追加一个整数。
• double findMedian() - 返回截至目前所有元素的中位数。

## 解题思路：

1. 大顶堆中存储的元素 均不大于 小顶堆中的元素
2. MaxHeap.size() == MinHeap.size()，或者 MaxHeap.size() == MinHeap.size() + 1

1. 当MaxHeap.size() == MinHeap.size() + 1时，中位数就是MaxHeap的堆顶元素
2. 当MaxHeap.size() == MinHeap.size()时，中位数就是MaxHeap堆顶元素与MinHeap堆顶元素的均值

## Python代码（使用heapq）：

``````from heapq import *
class MedianFinder:
def __init__(self):
"""
"""
self.minHeap = []
self.maxHeap = []

"""
Adds a num into the data structure.
:type num: int
:rtype: void
"""
heappush(self.maxHeap, -num)
minTop = self.minHeap[0] if len(self.minHeap) else None
maxTop = self.maxHeap[0] if len(self.maxHeap) else None
if minTop < -maxTop or len(self.minHeap) + 1 < len(self.maxHeap):
heappush(self.minHeap, -heappop(self.maxHeap))
if len(self.maxHeap) < len(self.minHeap):
heappush(self.maxHeap, -heappop(self.minHeap))

def findMedian(self):
"""
Returns the median of current data stream
:rtype: float
"""
if len(self.minHeap) < len(self.maxHeap):
return -1.0 * self.maxHeap[0]
else:
return (self.minHeap[0] - self.maxHeap[0]) / 2.0

# Your MedianFinder object will be instantiated and called as such:
# mf = MedianFinder()
# mf.findMedian()
``````

## Python代码：

``````import heapq
def __init__(self):
self.small = []  # the smaller half of the list, min-heap with invert values
self.large = []  # the larger half of the list, min heap

if len(self.small) == len(self.large):
heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))
else:
heapq.heappush(self.small, -heapq.heappushpop(self.large, num))

def findMedian(self):
if len(self.small) == len(self.large):
return float(self.large[0] - self.small[0]) / 2.0
else:
return float(self.large[0])

# 18 / 18 test cases passed.
# Status: Accepted
# Runtime: 388 ms
``````

## Python代码（手写堆）：

``````class Heap:
def __init__(self, cmp):
self.cmp = cmp
self.heap = [None]

def __swap__(self, x, y, a):
a[x], a[y] = a[y], a[x]

def size(self):
return len(self.heap) - 1

def top(self):
return self.heap[1] if self.size() else None

def append(self, num):
self.heap.append(num)
self.siftUp(self.size())

def pop(self):
top, last = self.heap[1], self.heap.pop()
if self.size():
self.heap[1] = last
self.siftDown(1)

def siftUp(self, idx):
while idx > 1 and self.cmp(idx, idx / 2, self.heap):
self.__swap__(idx / 2, idx, self.heap)
idx /= 2

def siftDown(self, idx):
while idx * 2 <= self.size():
nidx = idx * 2
if nidx + 1 <= self.size() and self.cmp(nidx + 1, nidx, self.heap):
nidx += 1
if self.cmp(nidx, idx, self.heap):
self.__swap__(nidx, idx, self.heap)
idx = nidx
else:
break

class MedianFinder:
def __init__(self):
"""
"""
self.minHeap = Heap(cmp = lambda x, y, a: a[x] < a[y])
self.maxHeap = Heap(cmp = lambda x, y, a: a[x] > a[y])

"""
Adds a num into the data structure.
:type num: int
:rtype: void
"""
self.maxHeap.append(num)
if self.minHeap.top() < self.maxHeap.top() \
or self.minHeap.size() + 1 < self.maxHeap.size():
self.minHeap.append(self.maxHeap.pop())
if self.maxHeap.size() < self.minHeap.size():
self.maxHeap.append(self.minHeap.pop())

def findMedian(self):
"""
Returns the median of current data stream
:rtype: float
"""
if self.minHeap.size() < self.maxHeap.size():
return self.maxHeap.top()
else:
return (self.minHeap.top() + self.maxHeap.top()) / 2.0

# Your MedianFinder object will be instantiated and called as such:
# mf = MedianFinder()
# mf.findMedian()
``````

Pingbacks已关闭。