前言

最近刷题刷到215. Kth Largest Element in an Array，找到数组中第 k 个最大的元素

解题

这个问题可以用堆解决。堆其实是一棵二叉树，如果根节点大于所有节点，就叫最大堆，反之叫最小堆。

可以用一个公式来表示，a[k]<=a[2k+1]，a[k]<=a[2k+2]，即第 k 个元素小于 2k+1 个和 2k+2 个，这是最小堆需要满足的条件，把小于改成大于就是最大堆了。

堆常用来排序和实现优先级队列，优先级队列就是只用堆有序的特性实现，可以看到PriorityQueue 的实现

python 解法

python 默认提供堆的数据结构实现

import heapq
from typing import List


class Solution:
    def __init__(self) -> None:
        self.minheap: List[int] = []

    def findKthLargest(self, nums: List[int], k: int) -> int:
        for i in nums:
            self.push(i)
        for _ in range(len(nums) - k):
            heapq.heappop(self.minheap)
        return heapq.heappop(self.minheap)

    def push(self, val: int) -> None:
        heapq.heappush(self.minheap, val)


if __name__ == "__main__":
    s = Solution()
    nums = [3, 2, 1, 5, 6, 4]
    k = 2
    print(s.findKthLargest(nums, k))  # 5
    s = Solution()
    nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]
    k = 4
    print(s.findKthLargest(nums, k))  # 4

看源码可以看到 heappush、heappop 之后，会调用_siftup、_siftdown，这是用来保持数组有续的。其实它实现了最大堆、最小堆，只是最大堆用的下划线开头的函数，表示不想被外部调用。

go 解法

go 提供了一个 container/heap，只需要实现Interface Len、Swap、Less 这三个接口就可以，

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeaq []int

func findKthLargest(nums []int, k int) int {
	temp := MaxHeaq(nums)
	h := &temp
	heap.Init(h)
	for i := 1; i < k; i++ {
		heap.Remove(h, 0)
	}
	return (*h)[0]
}

func (h MaxHeaq) Len() int {
	return len(h)
}

func (h *MaxHeaq) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeaq) Pop() interface{} {
	res := (*h)[len(*h)-1]
	*h = (*h)[0 : len(*h)-1]
	return res
}

func (h MaxHeaq) Less(i, j int) bool {
        // 最大堆，反之就是最小堆
	return h[i] > h[j]
}

func (h MaxHeaq) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func main() {
	nums := []int{3, 2, 1, 5, 6, 4}
	k := 2
	fmt.Println(findKthLargest(nums, k)) // 5
	nums = []int{3, 2, 3, 1, 2, 4, 5, 5, 6}
	k = 4
	fmt.Println(findKthLargest(nums, k)) //4
}

leetcode 215.Kth Largest Element in an Array

前言

解题

python 解法

go 解法

Reference

目录: