...
| Code Block | ||
|---|---|---|
| ||
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
h := newHeap(len(lists))
for _, l := range lists {
if l != nil {
heap.Push(h, l)
}
}
dummy := &ListNode{}
head := dummy
for h.Len() != 0 {
top := heap.Pop(h).(*ListNode)
head.Next = top
head = head.Next
if top.Next != nil {
heap.Push(h, top.Next)
top.Next = nil
}
}
return dummy.Next
}
type Heap []*ListNode
func newHeap(cap int) *Heap {
h := make(Heap, 0, cap)
return &h
}
func (h Heap) Len() int {
return len(h)
}
func (h Heap) Less(i, j int) bool {
return h[i].Val < h[j].Val
}
func (h Heap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *Heap) Push(x any) {
*h = append(*h, x.(*ListNode))
}
func (h *Heap) Pop() any {
l := len(*h)
v := (*h)[l-1]
*h = (*h)[:l-1]
return v
} |
LC 378. Kth Smallest Element in a Sorted Matrix 有序矩阵中第 K 小的元素
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/
合并 k 个有序列表 / 堆（只利用了单向递增）
略
二分
| Code Block | ||
|---|---|---|
| ||
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
// 二分：满足 count(mid) >= k 的最小值
L, R := matrix[0][0], matrix[n-1][n-1]
for L < R {
mid := L + (R - L) / 2
if count(matrix, mid) >= k {
R = mid
} else {
L = mid + 1
}
}
return L
}
// 返回 <=x 的元素数量 - O(n)
func count(matrix [][]int, x int) (c int) {
n := len(matrix)
i, j := 0, n-1
for i < n && j >= 0 {
if matrix[i][j] <= x {
c += j+1
i++
} else {
j--
}
}
return c
} |