347. 前 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 个高频元素的集合是唯一的。 你可以按任意顺序返回答案。
思路一：HashMap 计数 + 排序
使用hashmap对每个元素进行出现次数统计
对hashmap根据value进行排序，排序前要先把hashmap中的所有entry都存入到一个list中，只有在list中才可以使用Collections.sort()进行排序
保存前k个元素到数组
1 class Solution {
2 public int[] topKFrequent(int[] nums, int k) {
3 // 使用hashmap对每个元素进行出现次数统计
4 HashMap<Integer, Integer> map = new HashMap<>();
5 for(int num : nums){
6 if(map.containsKey(num)){
7 map.put(num, map.get(num)+1);
8 }else{
9 map.put(num, 1);
10 }
11 }
12
13 // 对hashmap根据value进行排序
14 // 先把hashmap中的所有entry都存入到一个list中，只有在list中才可以使用Collections.sort()进行排序
15 List<Map.Entry<Integer, Integer>> list = new ArrayList<>();
16 list.addAll(map.entrySet());
17
18 Collections.sort(list, new Comparator<Map.Entry<Integer,Integer>>(){
19 public int compare(Map.Entry<Integer,Integer> o1, Map.Entry<Integer,Integer> o2){
20 return o2.getValue() - o1.getValue();
21 }
22 });
23
24 // 保存前k个元素到数组
25 int[] res = new int[k];
26 int i = 0;
27 for(Map.Entry<Integer,Integer> en : list){
28 res[i++] = en.getKey();
29 if(i >= k){
30 break;
31 }
32 }
33 return res;
34 }
35 }
leetcode 执行用时：18 ms > 45.17%, 内存消耗：41.1 MB > 93.84%
复杂度分析：
时间复杂度：O(nlogn), 使用Hashmap进行计数的复杂度为O(n), 随后对hashmap进行排序，虽然其中的键值对可能没有n那么多，但是在最坏情况下键值对的个数为n, 所以排序的时间复杂度为O(nlogn)
空间复杂度：O(2n); 需要一个hashMap存储每个值出现的次数，键值对最大为O(n), 随后将所有健值对存入一个临时 list, 也花费了O(n)的空间，所以整体空间复杂度为O(2n)
思路二：HashMap计数 + 堆
这次仍然是先使用HashMap进行计数，然后维持一个大小为k的最小堆，最后取出堆中所有元素存入一个数组
1 class Solution {
2 public int[] topKFrequent(int[] nums, int k) {
3 // 使用hashmap对每个元素进行出现次数统计
4 HashMap<Integer, Integer> map = new HashMap<>();
5 for(int num : nums){
6 if(map.containsKey(num)){
7 map.put(num, map.get(num)+1);
8 }else{
9 map.put(num, 1);
10 }
11 }
12
13 // 然后维持一个大小为k的最小堆
14 PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
15 for(Integer key : map.keySet()){
16 queue.offer(key);
17 if(queue.size() > k){
18 queue.poll();
19 }
20 }
21
22 // 最后取出堆中所有元素存入一个数组
23 int[] res = new int[k];
24 for(int i = 0; i < k; i++){
25 res[i] = queue.poll();
26 }
27 return res;
28 }
29 }
leetcode 执行用时：18 ms > 45.17%, 内存消耗：41.2 MB > 90.21%
复杂度分析：
时间复杂度: O(nlogk)。hashMap计数的时间是O(n), 后面维持一个大小为k的堆的时间花费为O(nlogk), 所以整体时间复杂度为O(nlogk)。
空间复杂度：O(n+k)。需要一个最大为O(n)的map 和一个 O(k)的堆，所以时间复杂度O(n+k)。
思路二：HashMap计数 + 桶排序
先使用hashmap进行计数，然后创建一个大小为 (n + 1) 的列表 list(之所以是n+1， 因为如果所有元素都是同一个元素的话，那这个元素的出现次数就是n, 那下标就是n, 所以需要一个大小为n+1的列表，这个列表的每个元素被当成是一个桶，每个桶是一个小列表，hashmap的值作为下标，键作为桶里的值，这样这个 list 列表中就保存了每个出现次数的所有元素。最后从大小遍历这个list, 把不为空的子列表元素都加入到数组中
1 class Solution {
2 public int[] topKFrequent(int[] nums, int k) {
3 // 使用hashmap对每个元素进行出现次数统计
4 HashMap<Integer, Integer> map = new HashMap<>();
5 for(int num : nums){
6 if(map.containsKey(num)){
7 map.put(num, map.get(num)+1);
8 }else{
9 map.put(num, 1);
10 }
11 }
12
13 // 然后创建一个大小为 (n + 1) 的列表 list
14 // 这个列表的每个元素被当成是一个桶，每个桶是一个小列表，hashmap的值作为下标，键作为桶里的值，
15 // 这样这个 list 列表中就保存了每个出现次数的所有元素。
16 List<Integer>[] list = new List[nums.length+1];
17 for(Map.Entry<Integer, Integer> en : map.entrySet()){
18 if(list[en.getValue()]== null){
19 list[en.getValue()] = new ArrayList<Integer>();
20 }
21 list[en.getValue()].add(en.getKey());
22 }
23
24 // 最后从大小遍历这个list, 把不为空的子列表元素都加入到数组中
25
26 ArrayList<Integer> res = new ArrayList<>();
27 for(int i = nums.length; i >= 0 && res.size() < k; i--){
28 if(list[i] != null){
29 res.addAll(list[i]);
30 }
31 }
32 int[] arr = new int[k];
33 for(int i = 0; i < k; i++){
34 arr[i] = res.get(i);
35 }
36 return arr;
37 }
38 }
leetcode 执行用时：14 ms > 92.28%, 内存消耗：41.3 MB > 72.55%