在未排序的数组中找到第 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
思路
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| 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 }
|