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

Question

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

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

给定一个非空的整数数组，返回k个最频繁的元素.

例如，给定1,1, 1, 2，2,3和k=2，返回1，2。

注意:您可以假设k总是有效的，1≤k≤数的唯一元素。您的算法的时间复杂度必须优于O(n log )，其中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

编辑

正如@SergeyTachenov在这里指出的，结果向量可能返回多个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-statement：

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

if-statement就行了。