前 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
}