当前位置：首页 > news >正文

前 K 个高频元素

news 2025/7/12 16:46:34

前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

题解：

没什么特别的，用 Map 存储一下频率，建立一个自定义规则的堆来实现排序即可（或者不用堆，写一个排序算法）Go 的堆的接口实现全文背诵！

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; i++) {if (map.containsKey(nums[i])) {map.put(nums[i], map.get(nums[i]) + 1);} else {map.put(nums[i], 1);}}PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());for (Map.Entry<Integer, Integer> entry : map.entrySet()) {heap.offer(entry);}int[] ans = new int[k];for (int i = 0; i < k; i++) {ans[i] = heap.poll().getKey();}return ans;}
}

func topKFrequent(nums []int, k int) []int {hMap := map[int]int{}for _, num := range nums {hMap[num]++}h := &Heap{}heap.Init(h)for key, value := range hMap {heap.Push(h, [2]int{key, value})}ans := make([]int, k)for i := 0; i < k; i++ {ans[i] = heap.Pop(h).([2]int)[0]}return ans
}type Heap [][2]intfunc (h Heap) Len() int           { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i][1] > h[j][1] }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }func (h *Heap) Push(x any) {*h = append(*h, x.([2]int))
}func (h *Heap) Pop() any {old := *hn := len(old)x := old[n-1]*h = old[0 : n-1]return x
}