前 K 个高频元素

题解思路

本题要求在一个整数数组中找出出现频率最高的前 k 个元素，且数据量较大（最多 $10^5$），因此我们必须使用 高效的算法。

方法：哈希表 + 最小堆（TopK 问题经典解法）

1. 统计频率： 使用 哈希表（HashMap） 统计每个元素的出现次数，时间复杂度为 $O(n)$。

2. 维护前 K 个频率元素： 使用一个 最小堆（Python 中使用 heapq，Java 和 C++ 用优先队列）来保存前 K 个频率最高的元素。

   • 堆中存储的是 (频率, 元素)。
   • 如果堆的大小超过 k，则弹出频率最小的元素。

3. 输出结果： 最终堆中剩下的就是前 K 个高频元素，将其提取出来作为答案即可。

为什么使用最小堆？

因为我们只关心前 K 个元素，最小堆能保证：

• 堆顶始终是当前最小频率元素。
• 若加入的频率比堆顶大，就替换它。

复杂度分析

• 时间复杂度：

  • 统计频率：$O(n)$
  • 堆操作：最多进行 $O(n \log k)$
  • 总体时间复杂度：$O(n \log k)$

• 空间复杂度：$O(n)$（用于频率哈希表和堆）

Python 实现

import sys
import heapq
from collections import Counter

# 读取输入
n, k = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

# 1. 统计每个数字的出现频率
freq_map = Counter(nums)

# 2. 用最小堆维护前 k 个频率高的元素
min_heap = []
for num, freq in freq_map.items():
    heapq.heappush(min_heap, (freq, num))  # (频率, 元素)
    if len(min_heap) > k:
        heapq.heappop(min_heap)  # 移除频率最小的

# 3. 取出堆中的元素
result = [num for freq, num in min_heap]
print(' '.join(map(str, result)))

Java 实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] nums = new int[n];
        Map<Integer, Integer> freqMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
        }

        // 小顶堆按频率排序
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            heap.offer(new int[]{entry.getValue(), entry.getKey()});
            if (heap.size() > k) heap.poll();  // 超过 k 个就弹出最小的
        }

        List<Integer> result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll()[1]);
        }

        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

C++ 实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    unordered_map<int, int> freq;

    // 1. 读入数据，统计频率
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        freq[nums[i]]++;
    }

    // 2. 使用最小堆维护前 k 个频率高的元素
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    for (auto& [num, count] : freq) {
        minHeap.emplace(count, num);
        if (minHeap.size() > k) minHeap.pop();  // 保持堆大小为 k
    }

    // 3. 输出结果
    while (!minHeap.empty()) {
        cout << minHeap.top().second << " ";
        minHeap.pop();
    }
    return 0;
}

Leetcode 75.前K个高频元素-原题链接

题目内容

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

输入描述

• 第一行输入两个整数 n 和 k，其中 n 是数组 nums 的长度。
• 第二行输入 n 个整数，表示数组 nums。

输出描述

输出 k 个整数，表示前 k 个出现频率最高的元素，顺序不限。

样例1

输入

6 2
1 1 1 2 2 3

输出

1 2

样例2

输入

1 1
1

输出

1

提示

• $1 <= nums.length <= 10^5$
• $k$ 的取值范围是 [$1$, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 $k$个高频元素的集合是唯一的