347. Top K Frequent Elements - Bucket Sorting

题目详见:347. Top K Frequent Elements

PrioirtyQueue 的解法可以参考类似题 692 的解法:点这里

下面介绍最优解:Bucket Sorting

解法一 Bucket Sorting

思路

一个长度为 n 的数组,一个数字最低的频率为0,最高的频率为n。所以所有可能的频率情况为n。我们可以用一个 长度为 n + 1 的list 数组来记录属于不同频率的所有数字。比如 list[2] = {3, 4} 代表频率为 2 的数字有 3 和 4。

取前 k 个频率最高的元素时,我们仅需从 list 的最后开始遍历取数字,直到取满 k 个数字为止。

代码
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> res = new ArrayList<>();

        List<Integer>[] list = new ArrayList[nums.length + 1]; // Frequency array

        // 记录每个数字的频率
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 记录相应频率下的数字
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int freq = entry.getValue();
            if (list[freq] == null) list[freq] = new ArrayList<>();
            list[freq].add(entry.getKey());
        }

        // 添加 k 个频率最高的数字
        for (int i = nums.length; i >= 0 && res.size() < k; i--) {
            if (list[i] != null) res.addAll(list[i]);
        }

        return res;
    }
}
复杂度分析
  • 时间复杂度 O(n) – 第一个 for 循环 O(n), 第二个 for 循环 O(n), 第三个 for 循环 O(k).
  • 空间复杂度 O(n) – bucket 数组储存了所有 n 个数字的频率
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!