Daily bit(e) C++. Топ из k наиболее частых значений

Добавлено 30 сентября 2023 в 05:34

Daily bit(e) C++ #231, распространенная задача на собеседованиях: топ из k наиболее частых значений.

Сегодня мы рассмотрим распространенную задачу на интервью по C++: топ из k наиболее частых значений.

Дан список целых чисел в виде std::vector<int> и счетчик k, верните k самых частых значений в списке в любом порядке.

Вы можете предположить, что входные данные приводят к уникальному решению, и ваше решение должно работать быстрее, чем O(n*logn).

Например, для входных данных {1,3,1,2,5,3,4} и k==2 результат должен быть {1,3}.

Прежде чем прочитать решение, советую попытаться решить эту задачу самостоятельно. Вот ссылка на Compiler Explorer с парой тестовых случаев: https://compiler-explorer.com/z/7E5bjq8sb.

Решение

Эта задача созвучна задаче типа «Насколько хорошо вы знаете стандартную библиотеку?».

У нас есть всего несколько вариантов, поскольку нам нужно предоставить решение, которое будет работать быстрее, чем O(n*logn). Технически существует решение O(n) с использованием std::nth_element (т.е. алгоритм QuickSelect); однако QuickSelect имеет высокие постоянные накладные расходы. Вместо этого мы можем предоставить решение O(n*logk), для которого есть несколько вариантов:

упорядоченные контейнеры: std::priority_queue, std::set
алгоритмы кучи: std::push_heap, std::pop_heap
частичная сортировка: std::partial_sort, std::partial_sort_copy

В частности, использование std::partial_sort_copy позволяет нам реализовать простое двухэтапное решение.

std::vector<int> most_frequent_elements(
  const std::vector<int>& nums, int k) 
{
    // Вычисляем "частоты" элементов
    std::unordered_map<int,int> map;
    for (auto v : nums)
        ++map[v];

    // Изменяем размер result, чтобы он содержал k элементов
    std::vector<int> result(std::min(int64_t{k}, std::ssize(nums)));
    // Частично отсортируем ключи из map частот
    // в невозрастающем порядке на основе их частоты.
    std::ranges::partial_sort_copy(map | std::views::keys, result,
        [&map](int l, int r) {
            return map[l] > map[r];
        }
    );
    return result;
}

Открыть решение на Compiler Explorer.

Решение

Теги