Сортировать по частоте

Question

Я хочу сортировать элементы в массиве по их частоте.

Input: 2 5 2 8 5 6 8 8 

Output: 8 8 8 2 2 5 5 6 

Теперь одно решение это было бы:

• Сортировать элементы с помощью быстрой сортировки или сортировки слиянием. O (nlogn)
• Построить 2D-массив элемента и подсчитать путем сканирования отсортированного массива. O (n)
• Сортировка построенной 2D-массива в соответствии с подсчетом. O (nlogn)

Среди других возможных методов, которые я прочитал, используется двоичное дерево поиска, а другое - Хеширование.

Может ли кто-нибудь предложить мне лучший алгоритм? Я знаю, что сложность не может быть уменьшена. Но я хочу избежать так много обходов.

Answer 1

Вы можете выполнить один проход по массиву без его сортировки, а на отдельной структуре - подсчитать, сколько раз вы найдете элемент. Это можно сделать в отдельном массиве, если вы знаете диапазоны элементов, которые вы найдете, или в хеш-таблице, если вы этого не сделаете. В любом случае этот процесс будет O (n). Затем вы можете выполнить некоторую структуру сгенерированной второй структуры (где у вас есть счетчик), используя в качестве параметра сортировки сумму, связанную с каждым элементом. Этот второй процесс, как вы сказали, O (nlogn), если вы выберете правильный алгоритм.

Для этого второго этапа я бы рекомендовал использовать сортировку Heap с помощью очереди приоритетов. Вы можете указать очереди упорядочить элементы по атрибуту count (та, который был вычислен на первом шаге), а затем просто добавить элементы один за другим. Когда вы закончите добавлять, очередь будет уже отсортирована, и алгоритм имеет желаемую сложность. Чтобы получить ваши элементы, чтобы вы просто начали выскакивать.