엔지니어 게시판
LeetCode 솔루션 분류

# [8/2] 378. Kth Smallest Element in a Sorted Matrix

• 학부유학생 작성
• 작성일

• 147 조회
• 2 댓글

### 본문

Given an `n x n` `matrix` where each of the rows and columns is sorted in ascending order, return the `kth` smallest element in the matrix.

Note that it is the `kth` smallest element in the sorted order, not the `kth` distinct element.

You must find a solution with a memory complexity better than `O(n2)`.

Example 1:

```Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
```

Example 2:

```Input: matrix = [[-5]], k = 1
Output: -5
```

Constraints:

• `n == matrix.length == matrix[i].length`
• `1 <= n <= 300`
• `-109 <= matrix[i][j] <= 109`
• All the rows and columns of `matrix` are guaranteed to be sorted in non-decreasing order.
• `1 <= k <= n2`

• Could you solve the problem with a constant memory (i.e., `O(1)` memory complexity)?
• Could you solve the problem in `O(n)` time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.
Accepted
422,488
Submissions
698,944

댓글 2

## 학부유학생님의 댓글

• 학부유학생
• 작성일
Runtime: 314 ms, faster than 47.76% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 18.7 MB, less than 38.85% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.
``````
import heapq
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
min_heap = [(matrix[i][0], i, 0) for i in range(len(matrix)) ]

heapq.heapify(min_heap)

res = min_heap[0][0]
for _ in range(k):
res, i, j = heapq.heappop(min_heap)
if j + 1< len(matrix[0]):
heapq.heappush(min_heap,(matrix[i][j+1],i,j+1))

return res``````

## mingki님의 댓글

• mingki
• 작성일
C++
Runtime: 239 ms, faster than 5.03% of C++ online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 17 MB, less than 7.97% of C++ online submissions for Kth Smallest Element in a Sorted Matrix.
``````class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
vector<int> indice(n, 0);
priority_queue<vector<int>> heap;

for (int i = 0; i < n; ++i) {
heap.push(vector<int>{-matrix[i][0], i, 0});
}
vector<int> ptr;
while (k) {
ptr = heap.top(); heap.pop();
if (ptr[2] < n - 1) {
heap.push(vector<int>{-matrix[ptr[1]][ptr[2] + 1], ptr[1], ptr[2] + 1});
}
k--;
}
return -ptr[0];
}
};``````
전체 174 / 1 페이지

• 등록일 20:51
• 등록일 19:57
• 등록일 18:58
• 등록일 18:48
• 등록일 17:52
• 등록일 17:49
• 등록일 17:47
• 등록일 16:26
• 등록일 16:24
• 등록일 16:21
• 등록일 16:18
• 등록일 16:16
• 등록일 16:14
• 등록일 16:10
• 등록일 16:07
• 등록일 13:17

### 새댓글

• 등록자 학부유학생 등록일 08.08
• 등록자 학부유학생 등록일 08.08
• 등록자 학부유학생 등록일 08.07
• 등록자 학부유학생 등록일 08.05
• 등록자 진호 등록일 08.05
• 등록자 JKP 등록일 08.05
• 등록자 Joy 등록일 08.04
• 등록자 학부유학생 등록일 08.02
• 등록자 mingki 등록일 08.02
• 등록자 학부유학생 등록일 08.01
• 등록자 mingki 등록일 07.31
• 등록자 학부유학생 등록일 07.31
• 등록자 학부유학생 등록일 07.31
• 등록자 학부유학생 등록일 07.30
• 등록자 Eujin 등록일 07.29
• 등록자 학부유학생 등록일 07.28

### Stats

• 현재 접속자 99 명
• 오늘 방문자 784 명
• 어제 방문자 858 명
• 최대 방문자 1,338 명
• 전체 회원수 315 명