leetcode 215 数组中的第K个最大元素

题目

给定整数数组 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]  
}