首页 > 代码库 > 347. Top K Frequent Elements
347. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm‘s time complexity must be better than O(n log n), where n is the array‘s size.
思路：其实思路很简单。扫一遍array，把数和次数存到hashmap。然后按照次数大的priority把entry存到prioirty queue里面。最后按照k的个数依次从priority queue里面读出来。有Map.Entry这个神奇包裹省事很多。
Map.Entry:https://docs.oracle.com/javase/7/docs/api/java/util/Map.Entry.html
public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { List<Integer> save=new ArrayList<Integer>(); if(nums.length==0) { return save; } Map<Integer,Integer> res=new HashMap<Integer,Integer>(); for(int i=0;i<nums.length;i++) { if(!res.containsKey(nums[i])) { res.put(nums[i],1); } else { res.put(nums[i],res.get(nums[i])+1); } } PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>((a,b)->(b.getValue()-a.getValue())); for(Map.Entry<Integer,Integer> entry:res.entrySet()) { maxHeap.add(entry); } while(save.size()<k) { Map.Entry<Integer, Integer> entry = maxHeap.poll(); save.add(entry.getKey()); } return save; }}
347. Top K Frequent Elements
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。