LeetCode : 347. Top K Frequent Elements 根据频率选取topk元素

柔情只为你懂 2021-06-24 16:10 350阅读 0赞

**试题：**  
Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = \[1,1,1,2,2,3\], k = 2  
Output: \[1,2\]  
Example 2:

Input: nums = \[1\], k = 1  
Output: \[1\]  
Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.  
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.  
**代码：**  
堆排序，先统计频率，然后维持一个堆。

class Solution {
      public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> counter = new HashMap<>();
        for (int num: nums) {
          counter.put(num, counter.getOrDefault(num, 0)+1);
        }
    
        PriorityQueue<Integer> heap =
                new PriorityQueue<Integer>((n1, n2) -> counter.get(n1) - counter.get(n2));
    
        for (int num: counter.keySet()) {
          heap.add(num);
          if (heap.size() > k)
            heap.poll();
        }
    
        List<Integer> top_k = new LinkedList();
        while (!heap.isEmpty())
          top_k.add(heap.poll());
        Collections.reverse(top_k);
        return top_k;
      }
    }

桶排序

class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            Map<Integer,Integer> counter = new HashMap<>();
            for(int num: nums){
                counter.put(num,counter.getOrDefault(num,0)+1);
            }
            
            List<Integer>[] bucket = new ArrayList[nums.length+1];
            for(int key: counter.keySet()){
                int count = counter.get(key);
                if(bucket[count]==null){
                    bucket[count] = new ArrayList<>();
                }
                bucket[count].add(key);
            }
            
            List<Integer> topk = new ArrayList<Integer>();
            for(int i=bucket.length-1; i>0&&topk.size()<k; i--){
                if(bucket[i]==null) continue;
                if(bucket[i].size()<=(k-topk.size())){
                    topk.addAll(bucket[i]);
                }else{
                    topk.addAll(bucket[i].subList(0,k-topk.size()));
                }
            }
            return topk;
        }
    }