essay
hot100-数组中的第K个最大元素
#算法
hot100——数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
- 输入: [3,2,1,5,6,4], k = 2
- 输出: 5
示例 2:
- 输入: [3,2,3,1,2,4,5,5,6], k = 4
- 输出: 4
提示：
1 <= k <= nums.length <=
- <= nums[i] <=
解法
import "container/heap"
type MinHeap []int // 定义最小堆类型，底层使用切片
// --- 下面是必须实现的 heap.Interface 接口方法 ---
func (h MinHeap) Len() int { // Len 返回堆中元素的数量
return len(h)
}
func (h MinHeap) Less(i, j int) bool { // Less 定义堆的排序规则
return h[i] < h[j] // 对于最小堆，父节点的值应该小于子节点的值, 所以这里返回 h[i] < h[j]
}
func (h MinHeap) Swap(i, j int) { // Swap 交换两个索引位置的元素
h[i], h[j] = h[j], h[i]
}
func (h *MinHeap) Push(x interface{}) { // Push 向堆中添加元素注意, 接收者是指针类型 *MinHeap，因为我们要修改切片的长度
*h = append(*h, x.(int)) // 将 interface{} 类型断言为 int，然后追加到切片
}
func (h *MinHeap) Pop() interface{} { // Pop 从堆中移除并返回最后一个元素（堆顶）, 注意：接收者是指针类型 *MinHeap
top := (*h)[len(*h)-1] // 获取切片最后一个元素（即堆顶）(括号不能少)
*h = (*h)[:len(*h)-1] // 切片截取，移除最后一个元素(括号不能少)
return top
}
func findKthLargest(nums []int, k int) int {
h := &MinHeap{}
heap.Init(h) // 初始化堆，将切片调整为堆结构
for _, num := range nums {
if h.Len() < k { // 情况1：如果堆中元素数量还没达到 k，直接入堆
heap.Push(h, num)
} else if num > (*h)[0] { // 情况2：堆已满，且当前数字 num 大于堆顶元素（堆中最小的），说明 num 有资格进入“前 k 大”的行列，而堆顶应该被淘汰
heap.Pop(h) // 弹出堆顶（淘汰最小的）
heap.Push(h, num) // 新元素入堆
}
// 情况3：堆已满，但 num 小于等于堆顶，说明 num 不够大，直接忽略
}
return (*h)[0] // 遍历结束后，堆中保存的是最大的 k 个元素，堆顶 (*h)[0] 就是这 k 个元素中最小的，即整个数组的第 k 大元素（括号不能少）
}