题目
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
解答
方法一：优先队列
主要就分为以下几个步骤
- 要统计元素出现频率
- 对频率排序
- 找出前K个高频元素
python写法
class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: hush = {} for num in nums: hush[num] = hush.get(num,0)+1 heap = [] for key,freq in hush.items(): heapq.heappush(heap,(freq,key)) if len(heap)>k: heapq.heappop(heap) res = [] for _ in range(k): res.append(heapq.heappop(heap)[1]) return res
c++写法
我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素
class Solution { public: class mycomparsion{ public: bool operator()(const pair<int,int>& lhs,const pair<int,int>&rhs){ return lhs.second>rhs.second; } }; vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> map; for(int num:nums){ map[num]++; } priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparsion> pri_que; for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){ pri_que.push(*it); if(pri_que.size()>k){ pri_que.pop(); } } vector<int> res(k); for(int i=k-1;i>=0;i--){ res[i]=pri_que.top().first; pri_que.pop(); } return res; } };
修改了一下map遍历方式
// 小顶堆 class Solution { public: class mycomparsion{ public: bool operator()(const pair<int,int>& lhs,const pair<int,int>&rhs){ return lhs.second>rhs.second; } }; // 要统计元素出现频率 vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> map; for(int num:nums){ map[num]++; } // 对频率排序 // 定义一个小顶堆，大小为k priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparsion> pri_que; for(pair<int,int> it:map){ pri_que.push(it); if(pri_que.size()>k){ // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k pri_que.pop(); } } // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒叙来输出到数组 vector<int> res(k); for(int i=k-1;i>=0;i--){ res[i]=pri_que.top().first; pri_que.pop(); } return res; } };
另外一种写法
class Solution { public: bool static cmp(const pair<int,int>&a,const pair<int,int>&b){ return a.second>b.second; } vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> map; for(int num:nums){ map[num]++; } priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(&cmp)> pri_queue(cmp); for(pair<int,int> it:map){ pri_queue.push(it); if(pri_queue.size()>k){ pri_queue.pop(); } } vector<int> res(k); for(int i=k-1;i>=0;i--){ res[i]=pri_queue.top().first; pri_queue.pop(); } return res; } };
2022/3/2
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> map; for(int num:nums){ map[num]++; } struct cmp{ bool operator()(pair<int,int>& a,pair<int,int>& b)const{ return a.second<b.second; } }; priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q; for(const pair<int,int>& p:map){ q.push(p); } vector<int> res; for(int i=0;i<k;i++){ res.push_back(q.top().first); q.pop(); } return res; } };
java
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer,Integer> mp=new HashMap<>(); for(int i=0;i<nums.length;i++){ mp.put(nums[i],mp.getOrDefault(nums[i],0)+1); } PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>(){ @Override public int compare(Integer a,Integer b){ // if(mp.get(a)>mp.get(b)) return 1; // else return 0; if(mp.get(a)>mp.get(b)) return 1; else return -1; } }); for(Integer key:mp.keySet()){ if(pq.size()<k){ pq.add(key); }else if(mp.get(key)>mp.get(pq.peek())){ pq.remove(); pq.add(key); } } int res[]=new int[pq.size()]; int i=0; while(!pq.isEmpty()){ res[i++]=pq.remove(); } return res; } }
方法二：排序+暴力
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> map; for(int num:nums){ map[num]++; } vector<pair<int,int>> vec(map.begin(),map.end()); sort(vec.begin(),vec.end(),[](pair<int,int>&a,pair<int,int>&b){return a.second>b.second;}); vector<int> res; for(int i=0;i<k;i++){ res.push_back(vec[i].first); } return res; } };
