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.

复制代码

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. }

复制代码