347 前 K 个高频元素

一、题目

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

二、题解

方法一：哈希表 + 小顶堆

思路：使用 HashMap 统计每个元素出现的次数，再使用 PriorityQueue 小顶堆维护出现频率最高的 k 个元素。

1. 核心思路

由于题目要求返回出现频率前 k 高的元素，所以我们需要先统计每个数字出现的次数。

核心思想是：

  • 第一点：用 HashMap 统计每个数字出现的次数；
  • 第二点：用小顶堆保存当前频率最高的 k 个数字；
  • 第三点：当堆中元素超过 k 个时，弹出频率最小的元素。

这样遍历结束后，堆中剩下的就是前 k 个高频元素。

2. 具体步骤

  1. 使用 HashMap<Integer, Integer> 统计每个数字出现的次数。
  2. 创建一个小顶堆，堆中存放数字，排序规则按照数字出现频率从小到大排序。
  3. 遍历哈希表中的每个数字，将数字加入小顶堆。
  4. 如果堆的大小超过 k，就弹出堆顶元素，也就是当前频率最小的数字。
  5. 最后将堆中剩下的元素放入结果数组并返回。

3. 关键逻辑

PriorityQueue<Integer> heap = new PriorityQueue<>(
    (a, b) -> countMap.get(a) - countMap.get(b)
);

for (int num : countMap.keySet()) {
    heap.offer(num);

    if (heap.size() > k) {
        heap.poll();
    }
}

解释：

  • 小顶堆按照出现频率从小到大排序；
  • 堆顶永远是当前堆中频率最低的元素；
  • 如果堆大小超过 k，说明当前保留的元素太多了；
  • 此时弹出频率最低的元素，就可以保证堆中始终保留频率最高的 k 个元素。

4. 代码

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计每个数字出现的次数
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 2. 定义小顶堆
        // 堆中存放数字，按照数字出现频率从小到大排序
        PriorityQueue<Integer> heap = new PriorityQueue<>(
            (a, b) -> countMap.get(a) - countMap.get(b)
        );

        // 3. 遍历每个不同的数字
        for (int num : countMap.keySet()) {
            heap.offer(num);

            // 如果堆中元素超过 k 个，就移除频率最小的元素
            if (heap.size() > k) {
                heap.poll();
            }
        }

        // 4. 返回结果
        int[] result = new int[k];

        for (int i = 0; i < k; i++) {
            result[i] = heap.poll();
        }

        return result;
    }
}

5. 复杂度分析

时间复杂度：O(n+mlog⁡k)O(n + m \log k)

说明：

  • n 是数组 nums 的长度；
  • m 是数组中不同元素的个数；
  • 统计频率需要遍历数组一次，时间复杂度是 O(n)O(n)；
  • 每个不同元素最多入堆一次，堆的大小最多为 k，所以堆操作时间复杂度是 O(mlog⁡k)O(m \log k)。

空间复杂度：O(m+k)O(m + k)

说明：

  • HashMap 需要存储每个不同元素的出现次数，空间复杂度是 O(m)O(m)；
  • 小顶堆最多存储 k 个元素，空间复杂度是 O(k)O(k)。

方法二：哈希表 + 桶排序

思路：先用 HashMap 统计每个数字出现的次数，再根据出现次数把数字放入对应的桶中，最后从高频桶开始收集答案。

1. 核心思路

方法一使用小顶堆维护前 k 个高频元素，而方法二利用了一个特点：

一个数字在数组中最多出现 nums.length 次。

因此可以创建一个桶数组：

List<Integer>[] buckets = new List[nums.length + 1];

其中：

buckets[i]

表示出现次数为 i 的所有数字。

这种方法的核心是：

  • 先统计每个数字出现的次数；
  • 再按照出现次数把数字放入对应桶中；
  • 最后从频率最高的桶开始往前遍历，收集前 k 个数字。

2. 具体步骤

  1. 使用 HashMap<Integer, Integer> 统计每个数字出现的次数。
  2. 创建桶数组 buckets，数组下标表示出现次数。
  3. 遍历哈希表，将数字放入对应频率的桶中。
  4. 从 buckets.length - 1 开始往前遍历，也就是从最高频率开始遍历。
  5. 依次收集桶中的数字，直到收集到 k 个元素为止。
  6. 返回结果数组。

3. 关键逻辑

for (int i = buckets.length - 1; i >= 0; i--) {
    if (buckets[i] == null) {
        continue;
    }

    for (int num : buckets[i]) {
        result[index] = num;
        index++;

        if (index == k) {
            return result;
        }
    }
}

解释：

  • 从后往前遍历桶数组，表示从高频率到低频率遍历；
  • 如果当前桶为空，说明没有数字出现了这个次数，直接跳过；
  • 如果当前桶不为空，就依次取出里面的数字；
  • 当收集到 k 个元素时，直接返回结果。

4. 代码

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计每个数字出现的次数
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 2. 创建桶数组
        // 下标表示出现次数，buckets[i] 表示出现 i 次的所有数字
        List<Integer>[] buckets = new List[nums.length + 1];

        // 3. 把数字放入对应频率的桶中
        for (int num : countMap.keySet()) {
            int count = countMap.get(num);

            if (buckets[count] == null) {
                buckets[count] = new ArrayList<>();
            }

            buckets[count].add(num);
        }

        // 4. 从高频率到低频率收集结果
        int[] result = new int[k];
        int index = 0;

        for (int i = buckets.length - 1; i >= 0; i--) {
            if (buckets[i] == null) {
                continue;
            }

            for (int num : buckets[i]) {
                result[index] = num;
                index++;

                // 收集到 k 个元素后直接返回
                if (index == k) {
                    return result;
                }
            }
        }

        return result;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：

  • 统计频率需要遍历数组一次，时间复杂度是 O(n)O(n)；
  • 将数字放入桶中，最多处理所有不同元素，时间复杂度是 O(n)O(n)；
  • 从高频桶开始收集结果，最多遍历所有桶和所有元素，时间复杂度是 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：

  • HashMap 最多存储 n 个不同元素；
  • 桶数组长度是 nums.length + 1；
  • 所以空间复杂度是 O(n)O(n)。

评论