703. Kth Largest Element in a Stream

Question: Kth Largest Element in a Stream 

Solution

想法：

維護一組數字並固定 return 第 k 大的數字 → 只要記住 k 個數字就好了，並按照順序存這些數字

因為要 maintain size of k 的 list，return 第 k 大，所以從小排到大，每次 return 第 1 個數字，這樣最快: O(1)

再來分兩個部分：

1. 建立 data structure: initialize
   • 用 list 儲存資料由小排到大，用 selection sort 會花 O(n ^ 2) 的力氣
2. 新增數字: add
   • 排好之後的 list 要插入數字 O(n)，好一點用 binary search 找到插入的位置：O(log n)

有沒有辦法優化上述時間？ → 用 min Heap

• 建立 min Heap: O(log n)insert number into min Heap: O(log n)
• remove number from min Heap: O(log n)
• get min number from min Heap: O(1)

比 list 好很多！

實作 min Heap of size k：

• initialize: 如果 min Heap 的長度 > k，pop 最小值
• add: insert number into min Heap, if min Heap 長度 > k，pop 最小值，retrun min Heap[0]

import heapq

class KthLargest:

def __init__(self, k: int, nums: List[int]):

self.min_heap, self.k = nums, k

heapq.heapify(self.min_heap)

while len(self.min_heap) > self.k:

heapq.heappop(self.min_heap)

def add(self, val: int) -> int:

heapq.heappush(self.min_heap, val)

if len(self.min_heap) > self.k:

heapq.heappop(self.min_heap)

return self.min_heap[0]

Video Solution