给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。
解法一：
使用 Hashmap，建立数组中元素与其出现次数的映射。然后建立一个拥有 n 个列表的列表 lists，n 代表数组的长度，然后遍历 Hashmap，将出现次数相同的元素保存到同一个列表中，这里的列表为 lists 中下标为出现次数 -1 的列表。最后反向遍历 lists，将出现次数最大的 k 个元素加入 list 中。
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
List<List<Integer>> lists = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int max = 0;
for (int i = 0; i < nums.length; i++) {
if (!hashMap.containsKey(nums[i])) {
hashMap.put(nums[i], 1);
} else {
hashMap.replace(nums[i], hashMap.get(nums[i]) + 1);
}
}
Iterator iterator = hashMap.entrySet().iterator();
for (int i = 0; i < nums.length; i++) {
List<Integer> list1 = new ArrayList<>();
lists.add(list1);
}
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry) iterator.next();
max = Math.max(max, (Integer) entry.getValue());
lists.get((Integer) entry.getValue() - 1).add((Integer) entry.getKey());
}
for (int i = lists.size() - 1; i >= 0; i--) {
for (int j = 0; j < lists.get(i).size(); j++) {
if (list.size() == k) {
break;
}
list.add(lists.get(i).get(j));
}
}
return list;
}
解法二：
我们还可以使用优先队列来做，使用一个最大堆按照映射次数从大到小排列。这里我们需要自己创建一个 Pair 类，因为 Java 自身提供的 Pair 类是不支持元素比较的。我们还需要实现 Comparable 接口，需要注意的是 compareTo 方法： 如果返回值大于 0，则将大的数放后面；如果返回值等于 0，则不做任何处理；如果返回值小于 0，则将小的数放前面。就是说 java 默认的排序方式是升序排序，而我们要的是降序排序。代码如下：
public List<Integer> topKFrequent(int[] nums, int k) {
PriorityQueue<Pair> queue = new PriorityQueue<>();
HashMap<Integer, Integer> hashMap = new HashMap<>();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (!hashMap.containsKey(nums[i])) {
hashMap.put(nums[i], 1);
} else {
hashMap.replace(nums[i], hashMap.get(nums[i]) + 1);
}
}
Iterator iterator = hashMap.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry) iterator.next();
queue.add(new Pair((Integer) entry.getKey(), (Integer) entry.getValue()));
}
for (int i = 0; i < k; i++) {
list.add(queue.poll().getKey());
}
return list;
}
class Pair implements Comparable<Pair> {
private Integer key;
private Integer value;
public Pair(Integer key, Integer value) {
this.key = key;
this.value = value;
}
public Integer getValue() {
return value;
}
public Integer getKey() {
return key;
}
@Override
public int compareTo(Pair o) {
if (this.value > o.getValue()) {
return -1;
} else if (this.value < o.getValue()) {
return 1;
} else {
return 0;
}
}
}
