Kth Largest Element in an Array
LeetCode.iconhttps://leetcode.com/problems/kth-largest-element-in-an-array/
ソート無しでK番目に大きな値を出力せよ、の問題。
ソート無しという制約があるので、k番目まで格納できるヒープを作り、値を格納していく。
最後にルートノードを出力する。
code:select.go
// k番目まで格納できるヒープ
type minHeap []int
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return hi < hj }
func (h minHeap) Swap(i, j int) { hi, hj = hj, hi }
func (h *minHeap) Push(i any) { *h = append(*h, i.(int)) }
func (h *minHeap) Pop() any {
old := *h
n := old.Len()
popped := oldn-1
*h = old0:n-1
return popped
}
func findKthLargest(nums []int, k int) int {
h := &minHeap{}
for _, val := range nums {
heap.Push(h, val)
if h.Len() > k {
heap.Pop(h)
}
}
return (*h)0
}