Распечатайте список уникальных элементов в порядке их частоты появления

Однако, мне кажется, для этого должен быть гораздо более эффективный алгоритм, так как, вероятно, есть способ сортировки частот на лету.

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

Канонические решения для этих типов задач:

1. (Ваше предложение): Создайте карту, удалите дубликаты и отсортируйте по частоте
2. Аналогичен 1, но вместо карты — сортировать элементы, а найти количество повторений каждого элемента легко с помощью бинарного поиска.

Если вы используете Python, используйте класс collections.Counter и его счетчик. метод most_common()

from collections import Counter
counted = Counter([7, 4, 2, 4, 9, 6, 5, 6, 2, 0, 2, 1])
ordered = [value for value, count in counted.most_common()]
print(ordered)  # [2, 4, 6, 0, 1, 5, 7, 9]

Доступен источник, показывающий, что heapq используется в наиболее общий()

Сосредоточив внимание на требовании в вопросе возможного принятия ввода в виде потока целых чисел, одним из решений будет модифицированная сортировка вставками...

Создайте список (здесь именуемый countlist) списков, изначально пустых. Каждый раз, когда вы принимаете новое значение, итерируйте по убыванию каждый список в countlist, ища значение. Если вы найдете значение в countlist[i], удалите значение из текущего списка и вставьте его в countlist[i+1], при необходимости добавив новый список в countlist. Если вы так и не найдете значение, вставьте его в countlist[1].

Цель итерации по убыванию вместо возрастания состоит в том, что это позволяет вам поддерживать указатель на то место, куда значение будет вставлено в countlist[i], если вы найдете его в countlist[i-1]. Если вам не нужна подсортировка по значениям с одинаковым счетчиком, вы можете пропустить этот указатель и выполнить итерацию по возрастанию.

Я считаю, что этот алгоритм в целом O(n²). Обработка каждого нового значения — O(n), а результаты сортируются по ходу. В любой момент вы можете напечатать правильный порядок (на данный момент), итерируя по убыванию через countlist и печатая каждый список.

Пример запуска, используя пример в вопросе...

input: 7, 4, 2, 4, 9, 6, 5, 6, 2, 0, 2, 1

After accepting 7:
countlist[1] = 7

After accepting 4:
countlist[1] = 4, 7

After accepting 2:
countlist[1] = 2, 4, 7

After accepting 4:
countlist[1] = 2, 7
countlist[2] = 4

After accepting 9:
countlist[1] = 2, 7, 9
countlist[2] = 4

After accepting 6:
countlist[1] = 2, 6, 7, 9
countlist[2] = 4

After accepting 5:
countlist[1] = 2, 5, 6, 7, 9
countlist[2] = 4

After accepting 6:
countlist[1] = 2, 5, 7, 9
countlist[2] = 4, 6

After accepting 2:
countlist[1] = 5, 7, 9
countlist[2] = 2, 4, 6

After accepting 0:
countlist[1] = 0, 5, 7, 9
countlist[2] = 2, 4, 6

After accepting 2:
countlist[1] = 0, 5, 7, 9
countlist[2] = 4, 6
countlist[3] = 2

After accepting 1:
countlist[1] = 0, 1, 5, 7, 9
countlist[2] = 4, 6
countlist[3] = 2