Решение: Сортировка букв по частоте
На вход программе подаются строчные английские буквы. Ввод этих символов заканчивается точкой (другие символы, отличные от «.» и букв «a»..«z», во входных данных отсутствуют; в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка). Требуется написать эффективную программу, которая будет печатать буквы, встречающиеся во входной последовательности, в порядке уменьшения частоты их встречаемости. Каждая буква должна быть распечатана один раз. Точка при этом не учитывается.
Если какие-то буквы встречаются одинаковое число раз, то они выводятся в алфавитном порядке. Например, если на вход подаются символы batat., программа должна вывести atb.
Решение по шагам
5 шаговДля каждой из 26 строчных английских букв создаём счётчик. При чтении очередного символа до точки увеличиваем счётчик соответствующей буквы.
$$count[\operatorname{ord}(c)-\operatorname{ord}('a')] \mathrel{+}= 1$$После окончания ввода формируем последовательность всех букв алфавита. Сортируем её по двум критериям: сначала по убыванию частоты, затем по возрастанию самой буквы. Алфавитный порядок при равных частотах обеспечивается вторым ключом сортировки.
$$key(c)=(-count[c],c)$$Буквы с нулевой частотой не выводим. Остальные печатаем в полученном порядке без разделителей.
$$O(26\log 26)=O(1)$$Пример реализации на Python:
$$count=[0]*26 while True: c=input().strip() if c=='.': break count[ord(c)-ord('a')]+=1 letters='abcdefghijklmnopqrstuvwxyz' order=sorted(letters, key=lambda c: (-count[ord(c)-ord('a')], c)) print(''.join(c for c in order if count[ord(c)-ord('a')]>0))$$Для последовательности batat частоты букв равны: a — 2, t — 2, b — 1. Поэтому буквы a и t выводятся в алфавитном порядке, затем b: atb.
count = [0] * 26
while True:
c = input().strip()
if c == '.':
break
count[ord(c) - ord('a')] += 1
letters = 'abcdefghijklmnopqrstuvwxyz'
order = sorted(letters, key=lambda c: (-count[ord(c) - ord('a')], c))
print(''.join(c for c in order if count[ord(c) - ord('a')] > 0))
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Сортировка по возрастанию частоты вместо убывания.
Нарушение алфавитного порядка для букв с одинаковой частотой.
Вывод точки или букв, которые не встречались во входной последовательности.
Подсчёт частот с использованием квадратичного перебора вместо массива из 26 счётчиков.
Вывод каждой буквы несколько раз вместо однократного вывода.