【LeetCode热题100】【堆】前 K 个高频元素

叶茂林

发布于 2024-04-18 01:02:00

13900

代码可运行

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

运行总次数：0

代码可运行

题目链接：347. 前 K 个高频元素

要找出前K个出现频率最多的元素，可以先用哈希表存储每个元素出现的次数，然后建立一个容量为K的小顶堆，遍历哈希表找到更高频的元素入堆进行堆调整，最后堆里的元素就是前K个出现次数最多的元素

手写一个堆，就在答案容器基础上建堆，注意比较需要用哈希表比较

class Solution {
public:
    vector<int> ans;
    int heapSize;
    unordered_map<int, int> hash;

    void adjustHeap(int root) {
        int left = 2 * root + 1;
        int right = left + 1;
        int next = root;
        if (left < heapSize && hash[ans[left]] < hash[ans[next]])
            next = left;
        if (right < heapSize && hash[ans[right]] < hash[ans[next]])
            next = right;
        if (next != root) {
            swap(ans[next], ans[root]);
            adjustHeap(next);
        }
    }

    void buildHeap() {
        for (int i = heapSize / 2 - 1; i >= 0; --i)
            adjustHeap(i);
    }

    vector<int> topKFrequent(vector<int> &nums, int k) {
        this->heapSize = k;
        for (auto &num: nums)
            hash[num]++;
        auto &&start = hash.begin();
        while (k--) {
            ans.push_back(start->first);
            ++start;
        }
        buildHeap();
        while (start != hash.end()) {
            if (start->second > hash[ans[0]]) {
                ans[0] = start->first;
                adjustHeap(0);
            }
            ++start;
        }
        return ans;
    }
};