题目描述

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。


解题思路(桶排序):
设置若干个桶,每个桶存储出现频率相同的数。桶的下标表示数出现的频率,即第 i 个桶中存储的数出现的频率为 i。

  1. 充分利用List和HashMap的结构
  2. 用HashMap存储数组的元素和每个元素出现的次数
    map.put(num, map.getOrDefault(num, 0) + 1);
  3. List<Integer>[] list:将每个元素出现的次数作为数组的下标,数组值为该元素
    static List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList();
        HashMap<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }
        List<Integer>[] list = new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (list[count] == null) {
                list[count] = new ArrayList();
            }
            list[count].add(num);
        }
        for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
            if(list[i] == null) continue;
            res.addAll(list[i]);
        }
        return res;
    }

Q.E.D.