Самые частые слова
Составителю частотного словаря нужны k самых частых слов текста — по одному разу каждое, вместе с числом употреблений. Порядок строгий: сначала более частые; слова с одинаковым числом употреблений — по алфавиту. Алфавит здесь — порядок кодов Unicode, тот, в котором сравнивает строки Python и Go: буквы от а до я идут как обычно, а ё стоит после я.
Текст уже разбит на слова: это ряды строчных русских букв, разделённые пробелами и переводами строк. Второй пример — начало эпилога «Войны и мира», а среди закрытых тестов — весь эпилог и первая часть первого тома.
Вход
В первой строке k (1 ≤ k ≤ 1000). Дальше — текст: не больше 100 000 слов из строчных русских букв, через пробелы и переводы строк.
Выход
k строк (или меньше, если разных слов в тексте меньше k): слово и через пробел — сколько раз оно встретилось, в порядке, описанном выше.
Примеры
Пример 1
3 кот пёс кот ёж пёс кот ёж ель ель
кот 3 ель 2 пёс 2
Пример 2
5 эпилог часть первая прошло семь лет после го года взволнованное историческое море европы улеглось в свои берега оно казалось затихшим но таинственные силы двигающие человечество таинственные потому что законы определяющие их движение неизвестны нам продолжали свое действие несмотря на то что поверхность исторического моря казалась неподвижною так же непрерывно как движение времени двигалось человечество слагались разлагались различные группы людских сцеплений подготовлялись причины образования и разложения государств перемещений народов историческое море не как прежде направлялось порывами от одного берега к другому оно бурлило в глубине исторические лица не как прежде носились волнами от одного берега к другому теперь они казалось кружились на одном месте исторические лица прежде во главе войск отражавшие приказаниями войн походов сражений движение масс теперь отражали бурлившее движение политическими и дипломатическими соображениями законами трактатами эту деятельность исторических лиц историки называют реакцией описывая деятельность этих исторических лиц бывших по их мнению причиною того что они называют реакцией историки строго осуждают их все известные люди того времени от александра и наполеона до фотия шеллинга фихте шатобриана и проч проходят перед их строгим судом и оправдываются или осуждаются смотря по тому содействовали ли они прогрессу или реакции в россии по их описанию в этот период времени тоже происходила реакция и главным виновником этой реакции был александр тот самый александр который по их же описаниям был главным виновником либеральных начинаний своего царствования и спасения россии в настоящей русской литературе от гимназиста до ученого историка нет человека который не бросил бы своего камушка в александра за неправильные поступки его в этот период царствования он должен был поступить так то и так то в таком случае он поступил хорошо в таком дурно он прекрасно вел себя в начале царствования и во время го года но он поступил дурно дав конституцию польше сделав священный союз дав власть аракчееву поощряя голицына и мистицизм потом поощряя шишкова и фотия он сделал дурно занимаясь фронтовой частью армии он поступил дурно раскассировав семеновский полк и т д надо бы исписать десять листов для того чтобы перечислить все те упреки которые делают ему историки на основании того знания блага человечества которым они обладают что значат эти упреки те самые поступки за которые историки одобряют александра как то либеральные начинания царствования борьба с наполеоном твердость выказанная им в м году и поход го года не вытекают ли из одних и тех же источников условий крови воспитания жизни сделавших личность александра тем чем она была из которых вытекают и те поступки за
и 15 в 11 их 6 он 6 александра 4
Ограничения
- Время · Python
- 2000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Счёт слов — словарь. Самое интересное — порядок равных. Проверьте первый пример: у «ель», «пёс» и «ёж» поровну, по два, а в ответ проходят только два из них.
2Подсказка 2
Если вы взяли Counter.most_common(k), посмотрите, в каком порядке он выдаёт слова с одинаковым счётом. Подсказка — в его исходном коде: он вызывает heapq.nlargest с ключом-счётом.
3Идея
Нужен один ключ, который учитывает оба правила: пара (−счёт, слово). Меньшая пара — более частое слово, а при равном счёте — слово раньше по алфавиту. Тогда k лучших — это k наименьших пар, и их даёт куча из k: heapq.nsmallest(k, …, key=…), или сортировка всех пар, если разных слов немного.
4Разбор
Считаем слова словарём (Counter в Python, map в Go) и выбираем k наименьших по ключу (−счёт, слово). Эталон на Python берёт heapq.nsmallest — кучу из k; эталон на Go просто сортирует все пары: разных слов в тестах не больше нескольких тысяч.
Почему ошибается most_common. Он устроен как heapq.nlargest(k, items, key=счёт), а nlargest при равных ключах сохраняет порядок, в котором элементы пришли, — для Counter это порядок первого появления слова в тексте. В первом примере «пёс» появился раньше «ель», и most_common(3) выдаёт кот, пёс, ёж вместо кот, ель, пёс. Ошибку легко не заметить: на больших счётах равных почти нет, и вершина списка обычно верна. Ломается граница топа — там, где у многих слов одинаковые небольшие счёты.
Вторая ловушка — сама буква ё. По-русски «ёж» стоит между «ерш» и «жук», а в порядке кодов Unicode ё (U+0451) идёт после я (U+044F). Условие просит именно порядок кодов: его дают стандартные сравнения строк в Python и Go, и никакой локали не нужно.
4+Решение
5Сложность
Подсчёт — O(N) для N слов, выбор кучей — O(D log k) для D разных слов, сортировкой — O(D log D). Память — словарь на D слов.
6Типичные ошибки
Counter.most_common(k)— равные идут в порядке появления, а не по алфавиту.- Куча с ключом (счёт, слово) и выталкиванием минимума. Если держать кучу из k с наименьшей парой (счёт, слово) наверху, при равных счётах выталкивается слово, которое раньше по алфавиту, — а оно как раз должно остаться. Для равных нужен обратный порядок слов, поэтому проще работать с ключом (−счёт, слово) и
nsmallest. - Сортировка по-русски. Сравнение с учётом локали ставит ё рядом с е, а условие требует порядок кодов.
Алгоритмы задачи
O(n log k)
2 задачи
DS
Структура данных
Хеш-таблица
Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива.
O(1) в среднем
2 задачи