2021-11-12：前 K 个高频元素。给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。提示：1 <= nums.length <= 105，k 的取值范围是 [1, 数组中不相同的元素的个数]，题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。力扣347。
答案2021-11-12：
门槛堆。小根堆。
代码用golang编写。代码如下：
package mainimport ( "fmt" "sort")func main() { nums := []int{1, 1, 1, 2, 2, 3} k := 2 ret := topKFrequent(nums, k) fmt.Println(ret)}type Node struct { num int count int}func NewNode(k int) *Node { res := &Node{} res.num = k res.count = 1 return res}func topKFrequent(nums []int, k int) []int { map0 := make(map[int]*Node) for _, num := range nums { if _, ok := map0[num]; !ok { map0[num] = NewNode(num) } else { map0[num].count++ } } heap := make([]*Node, 0) for _, node := range map0 { if len(heap) < k || (len(heap) == k && node.count > heap[0].count) { //heap.add(node); heap = append(heap, node) sort.Slice(heap, func(i, j int) bool { return heap[i].count > heap[j].count }) } if len(heap) > k { heap = heap[1:] } } ans := make([]int, k) index := 0 for len(heap) > 0 { ans[index] = heap[0].num heap = heap[1:] index++ } return ans}执行结果如下：
左神java代码