#P4028. 前K个高频元素
-
ID: 2244
Tried: 569
Accepted: 205
Difficulty: 5
前K个高频元素
前 K 个高频元素
题解思路
本题要求在一个整数数组中找出出现频率最高的前 k
个元素,且数据量较大(最多 105),因此我们必须使用 高效的算法。
方法:哈希表 + 最小堆(TopK 问题经典解法)
-
统计频率: 使用 哈希表(HashMap) 统计每个元素的出现次数,时间复杂度为 O(n)。
-
维护前 K 个频率元素: 使用一个 最小堆(Python 中使用
heapq
,Java 和 C++ 用优先队列)来保存前 K 个频率最高的元素。- 堆中存储的是
(频率, 元素)
。 - 如果堆的大小超过
k
,则弹出频率最小的元素。
- 堆中存储的是
-
输出结果: 最终堆中剩下的就是前 K 个高频元素,将其提取出来作为答案即可。
为什么使用最小堆?
因为我们只关心前 K 个元素,最小堆能保证:
- 堆顶始终是当前最小频率元素。
- 若加入的频率比堆顶大,就替换它。
复杂度分析
-
时间复杂度:
- 统计频率:O(n)
- 堆操作:最多进行 O(nlogk)
- 总体时间复杂度:O(nlogk)
-
空间复杂度: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;
}
题目内容
给你一个整数数组 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<=105
- k 的取值范围是 [1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一,换句话说,数组中前 k个高频元素的集合是唯一的