LeetCode：前k高频数

题目：

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:

输入: nums = [1], k = 1 输出: [1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。 你可以按任意顺序返回答案。

来源：力扣（LeetCode）

解：

统计的话都可以，直接采用HashMap是比较方便的。关键在于怎么获得前k大，可以直接对次数排序，然后输出前k个，但是这样时间上就可能会在O（nlogn）。

这里采用数组存储前k大，每次进行k数组最小替换，所以时间上为(n-k)*k，加上优化，时间上就能达到较优。

class Solution { public int[] topKFrequent(int[] nums, int k) { //统计频次 HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>(); for(int x : nums){ if(hm.containsKey(x)){ hm.put(x,hm.get(x)+1); }else{ hm.put(x,1); } } //筛选前k大 int[] rs=new int[k]; int[] count=new int[k]; boolean flag=true; int c=0; for(Map.Entry<Integer,Integer> entry : hm.entrySet()){ //初始化 if(c<k){ rs[c]=entry.getKey(); count[c++]=entry.getValue(); continue; } //最小冒泡 if(flag){ for(int i=1;i<k;i++){ if(count[i]>count[i-1]){ int t=count[i]; count[i]=count[i-1]; count[i-1]=t; t=rs[i]; rs[i]=rs[i-1]; rs[i-1]=t; } } } if(entry.getValue()>count[k-1]){ rs[k-1]=entry.getKey(); count[k-1]=entry.getValue(); flag=true; }else{ //无修改，下次不用最小冒泡 flag=false; } } return rs; } }