001.数组中的第K个最大元素

• 215.数组中的第K个最大元素
  • 基于快速排序的选择方法
    • 时间复杂度：O(n)，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」
    • 空间复杂度：O(log⁡n)，递归使用栈空间的空间代价的期望为 O(log⁡n)
  • 基于堆排序的选择方法
    • 使用标准库的堆
    • 自己实现的堆
    • 时间复杂度：O(nlog⁡n)，建堆的时间代价是 O(n)，删除的总代价是 O(klog⁡n)，因为 k<n，故渐进时间复杂为 O(n+klog⁡n)=O(nlog⁡n)
    • 空间复杂度：O(log⁡n)，即递归使用栈空间的空间代价

数组中的第 K 个最大元素 - 使用标准库的堆

func findKthLargest(nums []int, k int) int {
	myMinHeap := &MinHeap{}
	heap.Init(myMinHeap)
 
	for _, num := range nums {
		heap.Push(myMinHeap, num)
		// 题目给定 k >= 1
		if myMinHeap.Len() == k + 1 {
			heap.Pop(myMinHeap)
		}
	}
 
	return heap.Pop(myMinHeap).(int)
}
 
type MinHeap []int
 
func (h MinHeap) Len() int {
	return len(h)
}
 
func (h MinHeap) Less(a, b int) bool {
	return h[a] < h[b]
}
 
func (h MinHeap) Swap(a, b int) {
	h[a], h[b] = h[b], h[a]
}
 
func (h *MinHeap) Push(val interface{}) {
	*h = append(*h, val.(int))
}
 
func (h *MinHeap) Pop() interface{} {
	n := h.Len()
	res := (*h)[n - 1]
	*h = (*h)[:n - 1]
	return res
}

数组中的第 K 个最大元素 - 自己实现的堆

func findKthLargest(nums []int, k int) int {
	myMinHeap := &MinHeap{}
 
	for _, num := range nums {
		myMinHeap.Push(num)
		// 题目给定 k >= 1
		if myMinHeap.Len() == k + 1 {
			myMinHeap.Pop()
		}
	}
 
	return myMinHeap.Pop()
}
 
type MinHeap []int
 
func (h MinHeap) Len() int {
	return len(h)
}
 
func (h *MinHeap) Push(val int) {
	*h = append(*h, val)
	h.up(h.Len() - 1)
}
 
func (h *MinHeap) Pop() int {
	n := h.Len()
	res := (*h)[0]
	h.swap(0, n - 1)
	*h = (*h)[:n - 1]
	h.down(0)
	return res
}
 
func (h MinHeap) up(idx int) {
	for {
		parent := (idx - 1) >> 1
		if parent < 0 {
			break
		}
		if h[idx] >= h[parent] {
			break
		}
		h.swap(parent, idx)
		idx = parent
	}
}
 
func (h MinHeap) down(idx int) {
	n := h.Len()
	for {
		left := idx << 1 + 1
		min := idx
		if left < n && h[left] < h[min] {
			min = left
		}
		if left + 1 < n && h[left + 1] < h[min] {
			min = left + 1
		}
		if min == idx {
			break
		}
		h.swap(min, idx)
		idx = min
	}
}
 
func (h MinHeap) swap(a, b int) {
	h[a], h[b] = h[b], h[a]
}