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

For example,

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.

解题思路

1. 用一个Map统计每个数字的出现频率。
2. 依据出现频率对Map.Entry进行排序，排序算法为堆排序。
3. 输出出现频率最高的k个元素。

实现代码

//Runtime: 43 mspublic class Solution {    private void buildHeap(ArrayList
     
      
       > entries, int root, int len) {        int left = 2 * root + 1;        if (left < len) {            int largest = left;            int right = left + 1;            if (right < len && entries.get(right).getValue() > entries.get(largest).getValue()) {                largest = right;            }            if (entries.get(root).getValue() < entries.get(largest).getValue()) {                Map.Entry
       
         entry = entries.get(root);                entries.set(root, entries.get(largest));                entries.set(largest, entry);                buildHeap(entries, largest, len);            }        }    }    private void heapSort(ArrayList
        
         
          > entries) {        int len = entries.size();        for (int i = len / 2; i >= 0; i--) {            buildHeap(entries, i, len);        }        for (int i = len - 1; i > 0; i--) {            Map.Entry
          
            entry = entries.get(0); entries.set(0, entries.get(i)); entries.set(i, entry); buildHeap(entries, 0, --len); } } public List
           
             topKFrequent(int[] nums, int k) { Map
            
              map = new HashMap
             
              (); for (int num : nums) { if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } ArrayList
              
               
                > entries = new ArrayList
                
                 
                  >(map.entrySet()); heapSort(entries); List
                  
                    list = new ArrayList
                   
                    (k); for (int i = entries.size() - 1; i >= entries.size() - k; i--) { list.add(entries.get(i).getKey()); } return list; }}