LeetCode 378. Kth Smallest Element in a Sorted Matrix 2019-08-20

题目描述

给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个元素。

你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

tag

矩阵题 二分

样例

1
2
3
4
5
6
7
8
9

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

返回 13。

算法1

(二分) O()
思路
复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
m = len(matrix)
n = len(matrix[0])

left = matrix[0][0]
right = matrix[-1][-1]

while left < right:

mid = (left + right) // 2
count = 0
i = m - 1
j = 0
while i >= 0 and j < n:
if matrix[i][j] <= mid:
count += i + 1
j += 1
else:
i -= 1

if count >= k:
right = mid
else:
left = mid + 1

return left

算法2

(堆) O()
思路
复杂度分析:
python 代码