...
| Code Block | ||
|---|---|---|
| ||
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
hv := make(CellHeap, 0, n)
h := &hv
for i := 0; i < n; i++ {
heap.Push(h, Cell{matrix[i][0], i, 0})
}
result := 0
for i := 0; i < k; i++ {
cell := heap.Pop(h).(Cell)
result = cell[0]
if cell[2] < n-1 {
r := cell[1]
c := cell[2]+1
heap.Push(h, Cell{matrix[r][c], r, c})
}
}
return result
}
type Cell [3]int
type CellHeap []Cell
func (h CellHeap) Len() int { return len(h) }
func (h CellHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h CellHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *CellHeap) Push(x any) { *h = append(*h, x.(Cell)) }
func (h *CellHeap) Pop() any {
l := h.Len()
v := (*h)[l-1]
(*h) = (*h)[:l-1]
return v
} |
思路：二分
| Code Block | ||
|---|---|---|
| ||
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
L, R := matrix[0][0], matrix[n-1][n-1]
for L < R {
mid := L + (R - L) / 2
c := count(matrix, mid)
if c >= k {
R = mid
} else {
L = mid + 1
}
}
return R
}
func count(matrix [][]int, x int) int {
n := len(matrix)
num := 0
i, j := n-1, 0
for i >= 0 && j < n {
if matrix[i][j] <= x {
num += i+1
j++
} else {
i--
}
}
return num
} |