Как min куча используется здесь, чтобы решить эту проблему

Question

Как min куча используется здесь, чтобы решить эту проблему

Я хотел бы знать, как 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;
}

1

algorithm c++min-heap

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Код работает так:

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 здесь Как min куча используется здесь, чтобы решить эту проблему, Ваш вектор результатов может вернуть более 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Заявление будет делать.

2