347. Top K Frequent Elements-白红宇

347. Top K Frequent Elements

阅读量：2351 次

发布时间：2019-05-10

本文共 1565 字，大约阅读时间需要 5 分钟。

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]

我的想法

用HashMap存频率，再根据频数进行快速排序或者归并排序。

但不知道怎样存元素，

class Solution {
       public List
   
     topKFrequent(int[] nums, int k) {
           HashMap
    
      map = new HashMap<>();        for(int i = 0; i < nums.length; i++) {
               if(map.containsKey(nums[i])) {
                   map.put(nums[i], map.get(nums[i]) + 1);            } else {
                   map.put(nums[i], 1);            }        }        //quicksort or mergesort    }}

解答

jiuzhang solution: Min Heap or 桶排序

HashMap的键值对可以用Map.Entry<E>来表示。把键值对存在一个PriorityQueue即堆中，poll出k个堆顶即为所求

class Solution {
       public List
   
     topKFrequent(int[] nums, int k) {
           if(nums == null || nums.length == 0) {
               return null;        }        HashMap
    
      map = new HashMap<>();        for(int i = 0; i < nums.length; i++) {
               if(map.containsKey(nums[i])) {
                   map.put(nums[i], map.get(nums[i]) + 1);            } else {
                   map.put(nums[i], 1);            }        }        //建立一个MaxHeap        PriorityQueue
     
      
       > heap = new PriorityQueue<>(            new Comparator
       
        
         >() { public int compare(Map.Entry
         
           e1, Map.Entry
          
            e2) { return e2.getValue() - e1.getValue(); } } ); for(Map.Entry
           
             entry : map.entrySet()) { heap.offer(entry); } List
            
              res = new ArrayList<>(); for(int i = 0; i < k; i++) { Map.Entry
             
               entry = heap.poll(); res.add(entry.getKey()); } return res; }}