Получить уникальные строки, упорядоченные по частоте появления

Условие

Создайте функцию, принимающую массив строк и возвращающую новый массив, содержащий только уникальные значения из исходного массива. При этом элементы должны быть отсортированы в порядке убывания количества их повторений в исходном наборе (от самых часто встречающихся к редким). При одинаковой частоте порядок между ними может быть произвольным.

Пример:

input_data = ["apple", "banana", "apple", "orange", "banana", "banana"]
# результат: ["banana", "apple", "orange"]

Функция должна работать за O(n log n) времени или лучше, где n — длина входного массива.

Ответ

Подсчитайте частоты строк, затем отсортируйте уникальные ключи по убыванию счётчика. Для примера получится banana, apple, orange.

from collections import Counter

def by_frequency(values):
    counts = Counter(values)
    return sorted(counts, key=counts.get, reverse=True)

Counter хранит по одной записи на уникальное значение. При k различных строках время составляет O(n + k log k), что укладывается в O(n log n), память O(k). Входной список не меняется. При одинаковой частоте порядок первого появления сохраняется стабильной сортировкой, хотя условие допускает любой.