Comment min tas est utilisé ici pour résoudre ce problème

Question

Je voudrais savoir comment min tas est utilisé ici pour résoudre le problème suivant.

Ce que j'ai pensé pour le résoudre est d'utiliser la hashtable et enregistrer les comptes des nombres. mais je ne sais pas comment utiliser le tas min pour contiune résoudre le problème.

Étant donné un tableau d'entiers non vides, renvoyez les k éléments les plus fréquents.

Par exemple, Étant donné [1,1,1,2,2,3] et k = 2, retour [1,2].

Remarque: Vous pouvez supposer que k est toujours valide, 1 ≤ k ≤ nombre d'éléments uniques. La complexité temporelle de votre algorithme doit être meilleure que O (n log n), où n est la taille du tableau.

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

Le code fonctionne comme ceci:

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

Comme indiqué par @SergeyTachenov ici How min heap is used here to solve this, votre vecteur de résultat peut revenir plus k éléments. Peut-être que vous pouvez résoudre ce problème en faisant:

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 
} 

Un autre petit commentaire

Vous n'avez pas vraiment besoin d'un while -Déclaration ici:

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

un if -Déclaration ferait.