---
# System prepended metadata

title: 'LeetCode #378 [Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/)'
tags: [Heap, LeetCode, Medium]

---

###### tags: `LeetCode` `Medium` `Heap`
# LeetCode #378 [Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/)
### (Medium)

給你一個 n x n 矩陣 matrix ，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。
請注意，它是 排序後 的第 k 小元素，而不是第 k 個 不同 的元素。

---
使用heap, 自動將輸入數字排序, 若heap數量大於k時, 將最大值pop掉。

在儲存全部元素後, 回傳heap的頂部元素(也就是全部元素中第k小的)即可。

---
```
class Solution {
public:
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        priority_queue<int> s;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                s.push(matrix[r][c]);
                if (s.size() > k) s.pop();
            }
        }
        return s.top();
    }
};

```