295. Find Median from Data Stream

Question: Find Median from Data Stream

Solution1 無腦 sort

python sort: Tim sort: Insertion sort O(n) ~ O(n^2) + Merge sort O(nlogn)

Time Complexity: O(nlogn)

import math

class MedianFinder:

def __init__(self):

self.len_num = 0

self.nums = list()

def addNum(self, num: int) -> None:

self.nums.append(num)

self.len_num += 1

def findMedian(self) -> float:

self.nums.sort()

if self.len_num % 2 == 0:

ind1 = int(self.len_num / 2)

ind2 = ind1 - 1

median = sum(self.nums[ind2: ind1 + 1]) / 2

else:

ind = int(math.floor(self.len_num / 2))

median = self.nums[ind]

return median

Solution2 Max Heap + min Heap

想法：

1. FindMedian: Median 是中間的數字，如果把 sorted list 拆成兩半看，就會是

   • 左邊 sorted list 的最大 → max Heap
   • 右邊 sorted list 的最小 → min Heap

   python 中只有 min Heap，所以左邊的 sorted list 要將 num * -1

   當要找出 median 時

   • 如果左邊 list 長度 == 右邊 list 長度：return (-left[0] + right[0]) / 2
   • 如果左邊 list 長度 > 右邊 list 長度: return -left[0]

   超級方便

   那麼麻煩的部分就是，在插入數字時 maintain 左右兩邊的 Heap

2. addNum:

1. 先看 num 是否比右邊最小的數字大
   1. 是：加到右邊 list，把右邊 list 最小，換到左邊 list
   2. 不是：直接加到左邊 list
2. 平衡兩邊 list 長度，如果兩邊 list 長度相差大於 1
1. heappop 左邊 list 的最小值 * -1，heappush 到右邊 list

Heap maintain Time Complexity: O(logn)

import heapq

class MedianFinder:

def __init__(self):

self.left_nums = list()

self.right_nums = list()

heapq.heapify(self.left_nums)

heapq.heapify(self.right_nums)

def addNum(self, num: int) -> None:

# check num > self.right_nums[0]

if self.right_nums and num > self.right_nums[0]:

heapq.heappush(self.right_nums, num)

ele = heapq.heappop(self.right_nums)

heapq.heappush(self.left_nums, -ele)

else:

heapq.heappush(self.left_nums, -num)

# balance

if len(self.left_nums) - len(self.right_nums) > 1:

ele = heapq.heappop(self.left_nums)

heapq.heappush(self.right_nums, -ele)

def findMedian(self) -> float:

if len(self.left_nums) > len(self.right_nums):

return -self.left_nums[0]

return (-self.left_nums[0] + self.right_nums[0]) / 2

Video Solution