LintCode Q80 Median in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2017年1月27日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import heapq
class MaxHeapObj(object):
def __init__(self, val):
self.val = val
# invert less than, the key to transform built-in min heap to
# max heap
def __lt__(self, other):
return self.val > other.val
def __eq__(self, other):
return self.val == other.val
def __str__(self):
return str(self.val)
class Solution:
"""
@param nums: A list of integers.
@return: An integer denotes the middle number of the array.
"""
def median(self, nums):
# write your code here
# heapq is a binary heap, with O(log n) push and O(log n) pop
max_heap = []
k = (len(nums) + 1) / 2
max_heap = []
for i in xrange(len(nums)):
if len(max_heap) == k:
if max_heap[0].val > nums[i]:
heapq.heappop(max_heap)
heapq.heappush(max_heap, MaxHeapObj(nums[i]))
else:
heapq.heappush(max_heap, MaxHeapObj(nums[i]))
return heapq.heappop(max_heap)
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。