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、解题思路:

方法思路

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

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

关键算法说明

1. ​快速选择优化

   • ​随机枢轴：通过rand()随机选择枢轴，避免输入有序时退化
   • ​分区操作：将数组分为两部分，左侧元素均满足比较条件
   • ​时间复杂度：平均O(n)，最坏O(n²)（但概率极低）

2. ​结果收集策略

   • ​两阶段收集：先收严格大于阈值的元素，再补充相等元素
   • ​保证数量：确保最终结果正好包含k个元素，处理频率相同的情况

3. ​数据结构选择

   • ​unordered_map：O(1)时间复杂度的频率统计
   • ​vector：方便进行快速选择操作