347. Top K Frequent Elements
解题思路；
O(n)
- hash，得到<元素，频次>键值对
- 因为频次小于n，建散列表，即新建大小为n+1的数组，数组下标为频次，数组内容为有相同频次的键值list，对散列表按下标由大到小遍历，找出k个键值
O(n*log(n-k))
- hash map
- 新建大小为n-k的最大堆，遍历<元素, 频次>，频次大于堆顶的保存到返回列表，频次小于堆顶的入堆，最后最小堆保存的是出现频次最低的n-k个，被“舍弃”的元素则是出现频次最大的k个
下边这段代码是根据上述第一种O(n)的思路写的代码。在LeetCode中运行时间是32ms
public static List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.get(nums[i])==null?1:map.get(nums[i])+1);
}
//定义类型为list的数组，此处并未对list进行初始化，数组下标为频率，对应的list的为此频率的element
ArrayList[] arrayList=new ArrayList[nums.length+1];
Iterator iterator=map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry entry=(Map.Entry) iterator.next();
if(arrayList[(int) entry.getValue()]==null)
arrayList[(int) entry.getValue()]=new ArrayList<>();//对list进行初始化
arrayList[(int) entry.getValue()].add(entry.getKey());
}
List<Integer> result = new ArrayList<Integer>();
//从后向前遍历arrayList，输出频率最高的前k个element
for(int i=arrayList.length-1;i>=0&&k>0;i--){
if(arrayList[i]==null)continue;
for(int j=0;j<arrayList[i].size()&&k>0;j++){
result.add((Integer)arrayList[i].get(j));
k--;
}
}
return result;
}
下面的代码是别人写的代码也是实现思路一的代码，和我写的步骤是一样的，不过要简洁一些
public static List<Integer> topKFrequent(int[] nums, int k) {
List<Integer>[] bucket = new List[nums.length + 1];
Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
for (int n : nums) {
frequencyMap.put(n, frequencyMap.get(n)==null?0: frequencyMap.get(n)+ 1);
}
for (int key : frequencyMap.keySet()) {
int frequency = frequencyMap.get(key);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList<>();
}
bucket[frequency].add(key);
}
List<Integer> res = new ArrayList<>();
for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) {
if (bucket[pos] != null) {
res.addAll(bucket[pos]);
}
}
return res;
}
参考原文：http://blog.csdn.net/lilingyu520/article/details/51339878
