Задача в Авито

Дан массив целых чисел и число k. Нужно вернуть k наиболее встречающиеся по частоте элементы.

Пример:
1 1 1 2 2 3
2
Вывод: 1 2

Решение:
Будем хранить частоту чисел в хеш-мапе, перенесем в вектор пары (частота, элемент), найдем K-ую порядковую статистику и отберем элементы с частотой >= пороговой

vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) freq[num]++;

vector<pair<int, int>> elements;
for (auto& [num, count] : freq)
elements.emplace_back(count, num);

auto kth = elements.begin() + k - 1;
nth_element(elements.begin(), kth, elements.end(),
[](auto& a, auto& b) { return a.first > b.first; });

int threshold = kth->first;
vector<int> result;
for (auto& [count, num] : elements)
if (count > threshold)
result.push_back(num);

for (auto& [count, num] : elements)
if (count == threshold && result.size() < k)
result.push_back(num);

return result;
}

Асимптотика О(N)

Кто не понял, это была проверка на адекватность

@algoses