378. 有序矩阵中第 K 小的元素
给你一个 n x n 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。
输入:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出:13
解释:矩阵中的元素为 [1,5,9,10,11,12,13,13,15],第 8 小元素是 13
//时间Onlog(r-l),空间O1,二分查找
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
left, right := matrix[0][0], matrix[n-1][n-1]
for left < right {
mid := left + (right - left) / 2
if check(matrix, mid, k, n) {
right = mid
} else {
left = mid + 1
}
}
return left
}
func check(matrix [][]int, mid, k, n int) bool {
i, j := n - 1, 0
num := 0
for i >= 0 && j < n {
if matrix[i][j] <= mid {
num += i + 1
j++
} else {
i--
}
}
return num >= k
}