在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
https://leetcode-cn.com/problems/kth-largest-element-in-an-array
思路
- 最小堆
type MinHeap struct {
arr []int
size int
}
func (m *MinHeap) Len() int {
return len(m.arr)
}
func (m *MinHeap) Less(i, j int) bool {
return m.arr[i] < m.arr[j]
}
func (m *MinHeap) Swap(i, j int) {
m.arr[i], m.arr[j] = m.arr[j], m.arr[i]
}
func (m *MinHeap) Push(v interface{}) {
m.arr = append(m.arr, v.(int))
}
func (m *MinHeap) Pop() interface{} {
t := m.arr[m.Len()-1] // 最后一个
m.arr = m.arr[0 : m.Len()-1]
return t
}
func (m *MinHeap) Top() int {
return m.arr[0] // 第一个
}
func (m *MinHeap) RealPush(v int) {
if m.size == m.Len() {
if m.Top() < v {
heap.Pop(m)
heap.Push(m, v)
}
} else {
heap.Push(m, v)
}
}
func InitHeap(size int) MinHeap {
m := MinHeap{
arr: make([]int, 0),
size: size,
}
heap.Init(&m)
return m
}
