$ cat ./coding/kth-smallest-element-in-a-sorted-matrix.md

────────────────────────────────────────────────────────────

378. Kth Smallest Element in a Sorted Matrix

題目的要求是找到在一個排序好的組合矩陣中，找到第 k 個最小的元素。

最簡單的方式當然就是全部排列出來後，再直接找到該元素，但是這樣的記憶體需求是 $O(n^2)$，題目希望我們可以用更少的記憶體來完成。

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        
        heap = []
        
        for i in range(len(matrix)):
            for j in range(len(matrix)):
                heapq.heappush(heap, -1 * matrix[i][j])
                if len(heap) > k:
                    heapq.heappop(heap)
        
        return heap[0] * -1

$ ls ./coding/ | grep -v kth-smallest-element-in-a-sorted-matrix