tags:
  - DSA

L5. Top K Frequent Elements (Star)

Description

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example:

Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]

Solution

提示：哈希表和优先队列（也就是堆）。

我的思路是，把这些数字都存储到哈希表中，这里我们用 std::unordered_map ，因为它要存储一个键值对，我们将重叠的数字作为键，将其出现的频次作为值。每一次出现相同的键，就将他的值进行加一操作，也就得到了该键出现的频次。

之后，将这个 map 结构放到一个 std::pair<int, int> 的优先队列里面，由于我们想要让堆来反应其最大频次，而在 C++ 中默认的堆是最大堆，我们将键值对中的值（也就是频次）作为优先队列的。最后按需求弹出 k 个频次最高的元素。

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

class mySolution{
public:
    std::vector<int> topK(const std::vector<int>& nums, const int& k ){
        std::unordered_map<int, int> map;
        for(auto elem : nums){
            map[elem] += 1;
        }
        std::vector<std::pair<int, int>> heap;
        for(std::pair<int, int> elem : map){
            heap.push_back({elem.second, elem.first});
        }
        std::make_heap(heap.begin(), heap.end());
        std::vector<int> res;
        for (int i = 0; i < k; i++) {
            std::pop_heap(heap.begin(), heap.end()); 
            res.push_back(heap.back().second);
            heap.pop_back();
        }
        return res;
    }
};

int main(){
    std::vector<int> nums = {1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 
                         6, 6, 6, 6, 6, 6, 7, 8, 9, 10, 10, 10, 11, 12};
    int k = 3;

    mySolution solution;
    std::vector<int> res = solution.topK(nums, k);
    for(auto elem : res){
        std::cout << elem << std::endl;
    }
    return 0;
}