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

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

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 ms
public class Solution {

    private void buildHeap(ArrayList<Map.Entry<Integer, Integer>> 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<Integer, Integer> entry = entries.get(root);
                entries.set(root, entries.get(largest));
                entries.set(largest, entry);
                buildHeap(entries, largest, len);
            }
        }
    }

    private void heapSort(ArrayList<Map.Entry<Integer, Integer>> 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<Integer, Integer> entry = entries.get(0);
            entries.set(0, entries.get(i));
            entries.set(i, entry);
            buildHeap(entries, 0, --len);
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        ArrayList<Map.Entry<Integer, Integer>> entries = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
        heapSort(entries);

        List<Integer> list = new ArrayList<Integer>(k);
        for (int i = entries.size() - 1; i >= entries.size() - k; i--) {
            list.add(entries.get(i).getKey());
        }
        return list;
    }
}