这里如何使用最小堆来解决这个问题

Question

我想知道这里是如何使用最小堆来解决下面的问题的。

我想解决这个问题的方法是使用哈希表并保存数字的计数。但是我不知道如何使用最小堆来继续解决问题。

给定一个非空整数数组，return k 个出现频率最高的元素。

例如，给定 [1,1,1,2,2,3] 和 k = 2，return [1,2].

注意：您可以假设 k 始终有效，1 ≤ k ≤ 唯一元素的数量。您的算法的时间复杂度必须优于 O(n log n)，其中 n 是数组的大小。

vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> counts;
        priority_queue<int, vector<int>, greater<int>> max_k;
        for(auto i : nums) ++counts[i];
        for(auto & i : counts) {
            max_k.push(i.second);
            // Size of the min heap is maintained at equal to or below k
            while(max_k.size() > k) max_k.pop();
        }
        vector<int> res;
        for(auto & i : counts) {
            if(i.second >= max_k.top()) res.push_back(i.first);
        }
        return res;
    }

Answer 1

代码是这样工作的：

for(auto i : nums) ++counts[i];  // Use a map to count how many times the
                                 // individual number is present in input

priority_queue<int, vector<int>, greater<int>> max_k;  // Use a priority_queue
                                                       // which have the smallest
                                                       // number at top

for(auto & i : counts) {
    max_k.push(i.second);                 // Put the number of times each number occurred
                                          // into the priority_queue

    while(max_k.size() > k) max_k.pop();  // If the queue contains more than
                                          // k elements remove the smallest
                                          // value. This is done because
                                          // you only need to track the k
                                          // most frequent numbers

vector<int> res;                                         // Find the input numbers
for(auto & i : counts) {                                 // which is among the most
    if(i.second >= max_k.top()) res.push_back(i.first);  // frequent numbers
                                                         // by comparing their
                                                         // count to the lowest of
                                                         // the k most frequent.
                                                         // Return numbers whose 
                                                         // frequencies are among
                                                         // the top k

EDIT

正如@SergeyTachenov 在这里所指出的，您的结果向量可能 return 多于 k 个元素。也许您可以通过以下方式解决此问题：

for(auto & i : counts) {
    if(i.second >= max_k.top()) res.push_back(i.first);
    if (res.size() == k) break; // Stop when k numbers are found
}

再来个小评论

你真的不需要while-声明：

while(max_k.size() > k) max_k.pop();

一个if语句就可以了。

这里如何使用最小堆来解决这个问题

How min heap is used here to solve this

c++

algorithm

min-heap