347. Top K Frequent Elements

yPhantom 2019年10月14日 26次浏览

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.

Solution

看到这种带范围的题目,使用桶排序。

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // 定义map,计算各个不同元素的出现次数
        Map<Integer, Integer> frequencyCount = new HashMap<>();
        for(int num: nums) {
            frequencyCount.put(num, frequencyCount.getOrDefault(num, 0) + 1);
        }
        // 定义桶,个数为length + 1,大小为1
        List<Integer>[] frequencyBrucket = new List[nums.length + 1];
        for (int key: frequencyCount.keySet()) {
            // 桶排序
            int frequency = frequencyCount.get(key);
            if (frequencyBrucket[frequency] == null) {
                frequencyBrucket[frequency] = new ArrayList<>();
            }
            frequencyBrucket[frequency].add(key);
        }
        // 逆序遍历所有的桶
        List<Integer> result = new ArrayList<>();
        for (int i = nums.length; i >= 0 && result.size() < k; i--) {
            if (frequencyBrucket[i] != null) {
                result.addAll(frequencyBrucket[i]);
            }
        }
        return result;
    }
}