目录

• 题目
• 思路1（哈希表与排序）
  • 代码
  • 复杂度分析
• 思路2（建堆）
  • 代码
  • 复杂度分析

题目

347. 前 K 个高频元素

思路1（哈希表与排序）

• 先用哈希表记录所有的值出现的次数
• 然后将按照出现的次数进行从高到低排序
• 最后取前 k 个就是答案了

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashtable = new HashMap<>();

        // 统计每个次数出现的次数
        for (int num : nums) {
            hashtable.put(num, hashtable.getOrDefault(num, 0) + 1);
        }

        // 排序
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(hashtable.entrySet());
        list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });

        // 获取前k高的结果
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = list.get(i).getKey();
        }

        return res;
    }
}

复杂度分析

• 时间复杂度：\(O(NlogN)\)，其中 N 为数组长度，遍历一遍花的时间是N，但是由于排序的时间复杂度是NlogN，所以总的时间复杂度为NlogN
• 空间复杂度：\(O(N)\)，其中 N 为数组长度

---

思路2（建堆）

• 也是先用哈希表统计出现的次数
• 然后利用小顶堆获取前k高的元素，堆操作的时间复杂度为logk，所以总的就是Nlogk

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 用哈希表存储出现次数
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int num : nums) {
            hashtable.put(num, hashtable.getOrDefault(num, 0) + 1);
        }

        // 使用优先队列
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        // 小顶堆，容量只为k，存储前n大的元素
        for (Map.Entry<Integer, Integer> entry : hashtable.entrySet()) {
            int element = entry.getKey();
            int count = entry.getValue();
            if (queue.size() == k) {
                // 保证队列存储的前k个元素出现频率都是最多的
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{element, count});
                }
            } else {
                queue.offer(new int[]{element, count});
            }
        }

        // 将优先队列元素出队转换为结果
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：\(O(Nlogk)\)，其中 N 为数组长度，由于堆的大小至多为 k，因此每次堆操作需要 O(logk) 的时间，共需 O(Nlogk) 的时间
• 空间复杂度：\(O(N)\)，其中 N 为数组长度