TopK问题
Top K 问题 是一类经典的算法问题，通常要求从一个数据集中找出最大或最小的 K 个元素。这类问题在面试和实际应用中非常常见，例如推荐系统、数据分析等场景。以下是解决 Top K 问题的常见方法及相关题目：
方法一：堆（优先队列）
思路
-
使用一个大小为 K 的最小堆（找最大 K 个元素）或最大堆（找最小 K 个元素）。
-
遍历数据集，将元素插入堆中，并保持堆的大小为 K。
-
最终堆中的元素即为 Top K。
时间复杂度
-
建堆的时间复杂度为 O(NlogK)O(NlogK)，其中 NN 是数据集的大小。
适用场景
-
数据集较大，且 K 远小于 N。
代码示例
#include <iostream>
#include <vector>
#include <queue>
std::vector<int> topKByHeap(std::vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 最小堆
for (int num : nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop(); // 保持堆的大小为 K
}
}
std::vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
return result;
}
int main() {
std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
int k = 3;
std::vector<int> result = topKByHeap(nums, k);
for (int num : result) {
std::cout << num << " ";
}
return 0;
}方法二：快速选择算法
思路
-
基于快速排序的分区思想，选择一个基准元素，将数据集分为两部分。
-
根据基准元素的位置，决定继续在左半部分或右半部分查找 Top K。
-
重复上述过程，直到找到 Top K。
时间复杂度
-
平均时间复杂度为 O(N)O(N)，最坏情况下为 O(N2)O(N2)。
适用场景
-
数据集较大，且对时间复杂度要求较高。
代码示例
#include <iostream>
#include <vector>
#include <algorithm>
int partition(std::vector<int>& nums, int left, int right) {
int pivot = nums[right]; // 选择最后一个元素作为基准
int i = left;
for (int j = left; j < right; j++) {
if (nums[j] >= pivot) { // 找最大 K 个元素
std::swap(nums[i], nums[j]);
i++;
}
}
std::swap(nums[i], nums[right]);
return i;
}
int quickselect(std::vector<int>& nums, int left, int right, int k) {
if (left == right) {
return nums[left];
}
int p = partition(nums, left, right);
if (p == k) {
return nums[p];
} else if (p < k) {
return quickselect(nums, p + 1, right, k);
} else {
return quickselect(nums, left, p - 1, k);
}
}
std::vector<int> topKByQuickselect(std::vector<int>& nums, int k) {
quickselect(nums, 0, nums.size() - 1, k - 1);
return std::vector<int>(nums.begin(), nums.begin() + k);
}
int main() {
std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
int k = 3;
std::vector<int> result = topKByQuickselect(nums, k);
for (int num : result) {
std::cout << num << " ";
}
return 0;
}总结：
1.创建一个大小为k的堆（大根堆 or 小根堆）
求最小 大根堆 ，求最大 小根堆
2.循环：
（1）依次进堆
（2）判断堆的大小是否超过K
3.思考：
用大根堆还是小根堆？？
为什么选择大根堆或者小根堆？？
| 方法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 排序法 | O(NlogN)O(NlogN) | 数据集较小 |
| 堆 | O(NlogK)O(NlogK) | 数据集较大，K 远小于 N |
| 快速选择 | O(N)O(N)（平均） | 数据集较大，对时间要求高 |
相关例题：
-
LeetCode 215. 数组中的第 K 个最大元素
-
题目链接：LeetCode 215
-
解法：堆或快速选择。
-
-
LeetCode 347. 前 K 个高频元素
-
题目链接：LeetCode 347
-
解法：哈希表统计频率 + 堆。
-
-
LeetCode 692. 前 K 个高频单词
-
题目链接：LeetCode 692
-
解法：哈希表统计频率 + 自定义排序。
-
-
LeetCode 973. 最接近原点的 K 个点
-
题目链接：LeetCode 973
-
解法：堆或快速选择。
-
例题： 前 K 个高频单词
1.题目解析
给定一个单词列表
words和一个整数k，返回前k个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序
2.示例
示例 1：
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出: ["i", "love"] 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。 注意，按字母顺序 "i" 在 "love" 之前。示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 输出: ["the", "is", "sunny", "day"] 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词， 出现次数依次为 4, 3, 2 和 1 次。
3.解题思路
1.预处理原始的字符串数组：用一个哈希表，统计一下每一个单词出现的频次
2.创建一个大小为k的堆
（1）频次：小根堆
（2）字典序：如果频次相同，使用大根堆
3.循环
（1）让每一个元素都循环入堆
（2）判断
4.输出结果
4.代码实现
class Solution {
public:
typedef pair<string, int> PSI;
struct cmp {
bool operator()(const PSI& a, const PSI& b) {
// 频次相同，字典序按照大根堆的方式
if (a.second == b.second) {
return a.first < b.first;
}
return a.second > b.second;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
// 统计一下每一个单词出现的频次
unordered_map<string, int> hash;
for (auto& s : words)
hash[s]++;
// 创建一个大小为K的堆
priority_queue<PSI, vector<PSI>, cmp> heap;
// TopK主逻辑
for (auto& psi : hash) {
heap.push(psi);
if (heap.size() > k)
heap.pop();
}
// 提取结果
vector<string> ret(k);
for (int i = k - 1; i >= 0; i--) {
ret[i] = heap.top().first;
heap.pop();
}
return ret;
}
};