LeetCode347. 前 K 个高频元素🌟🌟🌟🌟中等
课后作业
问题描述
原文链接：347. 前 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 <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
代码实现
Java
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//设置一个map集合,key存放数字,value存放出现次数
Map<Integer,Integer> map = new HashMap<>();
//统计出现次数
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//建立一个大根堆,用来存放key值,堆内元素按照key对应的value值从大到小排序
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b){
return map.get(a) - map.get(b);
}
});
//将map中的数字,插入到大根堆中
for(Integer key:map.keySet()){
if(queue.size() < k){
queue.add(key);
}else if(map.get(key) > map.get(queue.peek())){
queue.poll();
queue.add(key);
}
}
//将大根堆中的k个数字放到数组中
int [] res = new int[k];
int index = 0;
while(!queue.isEmpty()){
res[index++] = queue.poll();
}
return res;
}
}
Python
import heapq
from collections import Counter
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# 设置一个map集合,key存放数字,value存放出现次数
freq_map = Counter(nums)
# 建立一个小根堆,用来存放key值,堆内元素按照key对应的value值从大到小排序
heap = []
for key in freq_map:
if len(heap) < k:
heapq.heappush(heap, (freq_map[key], key))
elif freq_map[key] > heap[0][0]:
heapq.heappop(heap)
heapq.heappush(heap, (freq_map[key], key))
# 取出小根堆中的k个数字并返回
return [x[1] for x in heap]
C++
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
//设置一个map集合,key存放数字,value存放出现次数
unordered_map<int,int> map;
//统计出现次数
for(int num:nums){
map[num]++;
}
//建立一个小根堆,用来存放key值,堆内元素按照key对应的value值从大到小排序
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
//将map中的数字,插入到小根堆中
for(auto it = map.begin(); it != map.end(); it++) {
if(heap.size() < k){
heap.push(make_pair(it->second, it->first));
}else if(it->second > heap.top().first){
heap.pop();
heap.push(make_pair(it->second, it->first));
}
}
//将小根堆中的k个数字放到数组中
vector<int> res;
while(!heap.empty()){
res.push_back(heap.top().second);
heap.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
Go
type pair struct {
num int
count int
}
type priorityQueue []pair
func (pq priorityQueue) Len() int {return len(pq)}
func (pq priorityQueue) Swap(i, j int) {pq[i], pq[j] = pq[j], pq[i]}
func (pq priorityQueue) Less(i, j int) bool {return pq[i].count < pq[j].count}
func (pq *priorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(pair))
}
func (pq *priorityQueue) Pop() interface{} {
n := len(*pq)
x := (*pq)[n-1]
*pq = (*pq)[:n-1]
return x
}
func topKFrequent(nums []int, k int) []int {
//设置一个map集合,key存放数字,value存放出现次数
mapNums := make(map[int]int)
for _, num := range nums {
mapNums[num]++
}
//建立一个小根堆,用来存放key值,堆内元素按照key对应的value值从大到小排序
var pq priorityQueue
heap.Init(&pq)
for key, val := range mapNums {
if pq.Len() < k {
heap.Push(&pq, pair{num: key, count: val})
} else if val > pq[0].count {
heap.Pop(&pq)
heap.Push(&pq, pair{num: key, count: val})
}
}
//将小根堆中的k个数字放到数组中
var res []int
for pq.Len() > 0 {
res = append(res, heap.Pop(&pq).(pair).num)
}
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return res
}
评论(5)
打卡
https://leetcode.cn/problems/top-k-frequent-elements/solutions/2630950/347-qian-k-ge-gao-pin-yuan-su-by-yukisla-dgjq
优先队列
法二：
定义优先队列的排序规则
打卡