题目
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例
输入: [3,2,1,5,6,4], k = 2
输出: 5
解析
这题目一看就是让用堆来做，但目前对堆的实现原理还是理解的不深刻，就先使用go的heap包来进行实现。
同时还需要注意的是，求最大值用小顶堆，求最小值用大顶堆
// An IntHeap is a min-heap of ints.
type IntHeap []int func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x interface{}) { // Push and Pop use pointer receivers because the slice's length is part of the slice header, // which is passed by reference to the methods. *h = append(*h, x.(int))
} func (h *IntHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[:n-1] return x
} // findKthLargest 使用最小堆找到第k个最大的元素
func findKthLargest(nums []int, k int) int { if len(nums) == 0 || k < 1 || k > len(nums) { return -1 // 无效的输入 } h := &IntHeap{} heap.Init(h) // 填充堆，直到堆的大小达到k for _, num := range nums { heap.Push(h, num) if h.Len() > k { // 超过k个元素后，使用golang的堆自己弹出，不需要手动判断（当然手动判断也行，就是下面的方法）heap.Pop(h)} // if h.Len() < k { // heap.Push(h, num) // } else if num > (*h)[0] { // // 如果当前元素大于堆顶元素（即最小元素），则弹出堆顶元素并推入新元素 // heap.Pop(h) // heap.Push(h, num) // } } // 堆顶元素即为第k个最大的元素 return (*h)[0]
}
