これを解決するためにminヒープを使用する方法

Question

以下の問題を解決するためにここでminヒープを使用する方法を知りたいと思います。

私が解決すると考えたことは、ハッシュテーブルを使用して数値の数を保存することです。しかし、問題を解決するために最小のヒープをどのように使用するのか分かりません。

整数の空でない配列が与えられた場合、k個の最も頻繁な要素を返します。

たとえば、 [1,1,1,2,2,3]とk = 2の場合、[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

コードは次のように動作します。ここで@SergeyTachenovで指摘したようにHow min heap is used here to solve this

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

、あなたの結果ベクトルは、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を行うだろうが。