脚本宝典收集整理的这篇文章主要介绍了347. Top K Frequent Elements，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
My First PriorifyQueue Solution
This soltion use a Map to record the frequency of every number, and then use PriorityQueue to sort by frequency. The time complexity is O(nlogn), two pass.
class NumCount{ public NumCount(int num, int count){ this.num = num; this.count = count; } public int num=0; public int count = 0; } public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i++){ map.putIfAbsent(nums[i], 0); map.put(nums[i], map.get(nums[i])+1); } PriorityQueue<NumCount> queue = new PriorityQueue<>((a, b)->b.count-a.count); Set<Integer> set = map.keySet(); for(int num: set){ NumCount n = new NumCount(num, map.get(num)); queue.add(n); } int[] res = new int[k]; for(int i=0;i<k;i++){ res[i]=queue.poll().num; } return res; }
My Second Bucket Sort Solution
The time conplexity is O(n), because the sorting has been done when put the numbers in buckets.
public int[] topKFrequent(int[] nums, int k) { List<Integer>[] bucket = new List[nums.length+1]; Map<Integer, Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i++){ map.putIfAbsent(nums[i], 0); map.put(nums[i], map.get(nums[i])+1); } Set<Integer> set = map.keySet(); for(int num: set){ int freq = map.get(num); if(bucket[freq]==null){ bucket[freq]=new ArrayList<>(); } bucket[freq].add(num); } int[] res = new int[k]; int j=0; for(int i=bucket.length-1;i>=0;i--){ if(bucket[i]==null) continue; List<Integer> list = bucket[i]; for(int n: list){ if(j>=k) return res; res[j++]=n; } } return res; }
以上是脚本宝典为你收集整理的347. Top K Frequent Elements全部内容，希望文章能够帮你解决347. Top K Frequent Elements所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。