leetcode链接:
https://leetcode.cn/problems/kth-largest-element-in-an-array/...
解题思路:
应用一个小顶堆来存储以后曾经找到的前k大的数,如果遍历到一个新数时,它比堆顶元素大,那么就弹出堆顶元素,将新数退出堆中,保障堆中始终存储前k大的数。最终返回堆顶元素即可。
import ""container/heap"type TopList []intfunc (t TopList)Len()int{ return len(t)}func (t TopList)Swap(i,j int){ t[i],t[j] = t[j],t[i]}func (t TopList)Less(i,j int)bool{ return t[i]<t[j]}func (t *TopList)Push(x interface{}){ *t = append(*t,x.(int))}func (t *TopList)Pop()interface{}{ x := (*t)[len(*t)-1] *t= (*t)[:len(*t)-1] return x}func findKthLargest(nums []int, k int) int { m :=make(TopList,0) size :=0 for i:=range nums{ if size<k{ heap.Push(&m,nums[i]) size++ }else { if nums[i]>m[0]{//小顶堆 堆顶元素小于以后元素 heap.Pop(&m) heap.Push(&m,nums[i]) } } } return m[0]}