LeetCode-347. 前 K 个高频元素

1、题目描述:

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

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

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

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

2、代码:

使用stl自带的排序算法

#include <algorithm>
#include <unordered_map>
#include <utility>
#include <vector>using namespace std;class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 1. 统计每个数字的出现频率unordered_map<int, int> freq;for (auto& num : nums) {++freq[num]; // 遍历数组，统计频率}// 2. 将频率统计结果转为可排序的容器vector<pair<int, int>> elements;for (auto& [num, cnt] : freq) {elements.push_back({num, cnt}); // 格式：(数字，频率)}// 3. 定义降序比较规则（按频率排序）auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second; // 比较频率，降序排列};// 4. 快速选择算法：定位第k大的频率值// 将第k-1个元素放到排序后的正确位置，其左侧元素频率均 >= 它，右侧元素频率均 <= 它nth_element(elements.begin(), elements.begin() + k - 1, elements.end(), cmp);// 5. 获取第k大频率值（注意：pair结构为 (数字，频率)，取.second）int f = elements[k - 1].second;// 6. 收集结果vector<int> result;// 先收集所有频率严格大于f的元素（这些元素一定在前k名）for (auto& [num, cnt] : elements) {if (cnt > f) {result.push_back(num);}}// 补充频率等于f的元素，直到结果数量达到k（处理多个相同频率的情况）for (auto& [num, cnt] : elements) {if (cnt == f && result.size() < k) {result.push_back(num);}}return result;}
};

自定义一个快排( 菜鸟推荐 )

#include <cstdlib>       // 用于 rand() 函数
#include <unordered_map> // 用于哈希表统计频率
#include <vector>        // 用于动态数组存储元素
using namespace std;class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 阶段1: 统计每个数字的出现频率unordered_map<int, int> freq; // 哈希表存储(数字,出现次数)for (auto& num : nums) {++freq[num]; // 遍历数组统计频率，O(n)时间复杂度}// 阶段2: 准备可排序的数据结构vector<pair<int, int>> elements; // 存储格式(数字,频率)for (auto& [num, cnt] : freq) {elements.push_back({num, cnt}); // 将哈希表项转为可排序的vector}// 阶段3: 定义降序比较规则auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second; // 按频率值降序排列};// 阶段4: 快速选择算法定位第k大的元素// 目标是将第k-1个元素放到正确位置（索引从0开始）quickSelect(elements, 0, elements.size() - 1, k - 1, cmp);// 阶段5: 确定频率阈值int f = elements[k - 1].second; // 获取第k大元素的频率值// 阶段6: 收集最终结果vector<int> result;// 步骤1: 收集所有严格大于阈值f的元素for (auto& [num, cnt] : elements) {if (cnt > f) {result.push_back(num);}}// 步骤2: 补充频率等于f的元素直到填满k个for (auto& [num, cnt] : elements) {if (cnt == f && result.size() < k) {result.push_back(num);}}return result;}private:/* 快速选择算法实现参数说明:- elements: 待处理元素数组(会被部分排序)- left/right: 当前处理的区间范围- k: 目标排序位置(最终要确定位置的索引)- cmp: 自定义比较函数 */template <typename Compare>void quickSelect(vector<pair<int, int>>& elements, int left, int right,int k, Compare cmp) {// 递归终止条件：区间只剩一个元素if (left >= right) return;// 随机选择枢轴并交换到区间末尾// 避免输入有序时退化为O(n²)时间复杂度int pivot_idx = left + rand() % (right - left + 1);swap(elements[pivot_idx], elements[right]);// 分区操作：将大于枢轴的元素移到左半部分int i = left; // 分界指针，i左侧都是符合cmp条件的元素for (int j = left; j < right; j++) {// 使用自定义比较规则：elements[j]是否应该在枢轴前if (cmp(elements[j], elements[right])) {swap(elements[i++], elements[j]); // 符合条件则交换到i位置}}// 将枢轴放到正确位置（i此时是分界点）swap(elements[i], elements[right]);// 递归处理子区间if (k == i) return;          // 找到目标位置else if (k > i)              // 目标在右半区间quickSelect(elements, i + 1, right, k, cmp);else                         // 目标在左半区间quickSelect(elements, left, i - 1, k, cmp);}
};

3、解题思路:

方法思路

统计频率：使用哈希表统计每个元素的出现次数。
快速选择：将频率和对应的元素存储为列表，使用快速选择算法找到第k大的频率。
收集结果：根据第k大的频率值，收集所有频率大于或等于该值的元素，直到收集到k个元素。
stl自带的快排解释：

nth_element(
elements.begin(), // 范围的起点
elements.begin() + k-1, // 要确定正确位置的元素（第k大的位置）
elements.end(), // 范围的终点
cmp // 比较规则：降序排列（频率大的在前）
);

关键算法说明

快速选择优化
- 随机枢轴：通过rand()随机选择枢轴，避免输入有序时退化
- 分区操作：将数组分为两部分，左侧元素均满足比较条件
- 时间复杂度：平均O(n)，最坏O(n²)（但概率极低）
结果收集策略
- 两阶段收集：先收严格大于阈值的元素，再补充相等元素
- 保证数量：确保最终结果正好包含k个元素，处理频率相同的情况
数据结构选择
- unordered_map：O(1)时间复杂度的频率统计
- vector：方便进行快速选择操作