前 K 个高频元素（手写堆排序）

347. 前 K 个高频元素 - 力扣（LeetCode）

题目描述

给你一个整数数组 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 个高频元素的集合是唯一的

class Solution {
private:
    vector<pair<int,int>> fre;
    vector<int> res;
    unordered_map<int,int> map;
    //大根堆调整
    void headAdjust(vector<pair<int,int>>& heap, int k, int n) {
        pair<int,int> p = heap[k];
        for (int i = 2 * k + 1; i < n; i = 2 * i + 1) {
            if (i + 1 < n&& heap[i + 1].second > heap[i].second) {
                i++;
            }
            if (p.second >= heap[i].second) {
                break;
            }
            heap[k]= heap[i];
            k = i;
        }
        heap[k] = p;
    }
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //数字频率统计
        for(int num:nums)
            map[num]++;
        for(auto it:map)
            fre.emplace_back(it.first,it.second);
 
        //建立大根堆
        int n=fre.size();
        for(int i=(n>>1)-1;i>=0;i--)
            headAdjust(fre,i,n);
 
        //堆排序并调整，收集结果
        for (int i = n - 1; i >= n - k; i--) {
            res.push_back(fre[0].first);
            fre[0] = fre[i];
            headAdjust(fre, 0, i);
        }
        return res;
    }
};