leetcode 347. Top K Frequent Elements

Seawolf

1. Given a non-empty array of integers, return the k most frequent elements.
   
2. 
   
3. Example 1:
   
4. 
   
5. Input: nums = [1,1,1,2,2,3], k = 2
   
6. Output: [1,2]
   
7. Example 2:
   
8. 
   
9. Input: nums = [1], k = 1
   
10. Output: [1]
    
11. Note:
    
12. 
    
13. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
    
14. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

复制代码

using regular hashmap!

1. import java.util.Collection;
   
2. class Solution {
   
3.     public List<Integer> topKFrequent(int[] nums, int k) {
   
4.         List<Integer> list = new ArrayList<>();
   
5.         HashMap <Integer,Integer> map = new HashMap<>();
   
6.         for(int i = 0; i< nums.length; i++){
   
7.             map.put(nums[i], map.getOrDefault(nums[i],0)+1);
   
8.         }
   
9.         Collection<Integer> c = map.values();
   
10.         Object[] obj = c.toArray();
    
11.         Arrays.sort(obj);
    
12.         int i = 0;
    
13.         while(k-- != 0){
    
14.             for(Integer key : map.keySet()){
    
15.                 if (map.get(key).equals(Integer.parseInt(obj[obj.length- 1-i].toString())))
    
16.                 {
    
17.                     
    
18.                     i++;
    
19.                     list.add(key);
    
20.                     map.remove(key);
    
21.                     break;
    
22.                 }   
    
23.             }
    
24.         }
    
25.         return list;
    
26.     }
    
27. }

复制代码

using bucket sort!!

1. class Solution {
   
2.     public List<Integer> topKFrequent(int[] nums, int k) {
   
3.         Map<Integer,Integer> map = new HashMap<>();
   
4.         for(int a : nums) map.put(a,map.getOrDefault(a,0)+1);
   
5.         List<Integer> [] bucket = new List[nums.length + 1];
   
6.         
   
7.         for(Integer key : map.keySet()){
   
8.             
   
9.             int fre = map.get(key);
   
10.             if(bucket[fre] == null) bucket[fre] = new ArrayList<>();
    
11.             bucket[fre].add(key);
    
12.         }
    
13.         List<Integer> re = new ArrayList<>();
    
14.         
    
15.         for(int i = bucket.length - 1; i >=0 && re.size() < k ; i--){
    
16.             
    
17.             if(bucket[i] != null) re.addAll(bucket[i]);
    
18.         }
    
19.         
    
20.         return re;
    
21.         
    
22.     }
    
23.    
    
24. }

复制代码

using java heap!

1. import java.util.*;
   
2. class Solution {
   
3.    
   
4.     class Pair{
   
5.         int num;
   
6.         int count;
   
7.         public Pair(int num, int count){
   
8.             
   
9.             this.num = num;
   
10.             this.count =count;
    
11.         }
    
12.     }
    
13.     public List<Integer> topKFrequent(int[] nums, int k) {
    
14.         
    
15.         Map<Integer, Integer> map = new HashMap<>();
    
16.         
    
17.         for(int a: nums) map.put(a,map.getOrDefault(a,0)+1);
    
18.         
    
19.         PriorityQueue<Pair> queue = new PriorityQueue<Pair>(new Comparator<Pair>(){
    
20.             
    
21.             public int compare(Pair a, Pair b){
    
22.                
    
23.                 return a.count- b.count;
    
24.             }
    
25.         });
    
26.         
    
27.         for(Map.Entry<Integer,Integer> entry: map.entrySet()){
    
28.             
    
29.             Pair p = new Pair(entry.getKey(), entry.getValue());
    
30.             
    
31.             queue.offer(p);
    
32.             if(queue.size() > k) queue.poll();
    
33.         }
    
34.         
    
35.         List<Integer> list = new ArrayList<>();
    
36.         
    
37.         while(queue.size()>0) list.add(queue.poll().num);
    
38.         
    
39.         Collections.reverse(list);
    
40.         
    
41.         return list;
    
42.     }
    
43.    
    
44. }

复制代码