前 K 个高频元素

原题链接

使用的方法

桶排序

解题思路

• 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
• 我们可以使用桶排序的方法来解决这个问题。首先，我们需要统计每个元素出现的频率，并将这些频率存储在一个哈希表中。
• 接下来，我们可以创建一个桶数组，其中桶的索引表示元素出现的频率，桶中的元素是具有相同频率的元素列表。由于频率的最大值不会超过数组的长度，我们可以将桶数组的大小设置为 n + 1，其中 n 是输入数组的长度。
• 最后，我们从桶数组的末尾开始遍历，收集出现频率最高的元素，直到我们收集到 k 个元素为止。这样，我们就可以得到出现频率前 k高的元素。

代码实现

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int maxCnt = Collections.max(cnt.values());

        List<Integer>[] buckets = new ArrayList[maxCnt + 1];
        Arrays.setAll(buckets, _ -> new ArrayList<>());
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            buckets[e.getValue()].add(e.getKey());
        }

        int[] ans = new int[k];
        int j = 0;
        for (int i = maxCnt; j < k; i--) {
            for (int x : buckets[i]) {
                ans[j++] = x;
            }
        }
        return ans;
    }
}