【原题】 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]
.
【解释】
返回数组中出现最频繁的k个元素。
【思路】
思路一、hashmap统计频次,再对hashmap的value进行排序,取前面的k个最频繁的数。思路很简单,hashmap的value进行排序的过程,参照这里。
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer,Integer> hash=new HashMap<>();
List<Integer> list=new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
//可以使用hash.put(nums[i], hash.containsKey(nums[i])? hash.get(nums[i]) + 1 : 1);语句代替
if(hash.containsKey(nums[i]))
hash.put(nums[i], hash.get(nums[i])+1);
else hash.put(nums[i],1);
}
Comparator<Map.Entry<Integer, Integer>> byMapValues = new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> left, Map.Entry<Integer, Integer> right) {
return right.getValue().compareTo(left.getValue());//按照单词频率逆序排列
}
};
List<Map.Entry<Integer, Integer>> sortedListMap = new ArrayList<Map.Entry<Integer, Integer>>(hash.entrySet());
Collections.sort(sortedListMap, byMapValues);
for(int i=0;i<k;i++)
list.add(sortedListMap.get(i).getKey());
return list;
}
}
思路二、使用堆 java中PriorityQueue就是使用堆的思想来维护一个优先级。 没什么好说的,看这里吧。