Задать вопрос

Какую сортировку применять?

Предисловие:
Нашел интересную задачу в интернете погуглив, понял что такое на тестировании перед собеседованием.
391b33ff5b2e47289ad7c4e154e7a2ab.png
Вопрос:
Задача мне ясна, как я понял она упирается в сортировку, саму задачу я решил. Но вот сделать, чтобы она выполнялась в указанные 1-10 секунд не получается. Как я понял, надо делать сортировку у которой скорость log2(N). Не могли бы подсказать, на какой стадии лучше делать(Когда словарь только заполняется или сразу как он заполнился или когда нужные слова нашлись) сортировку и какую сортировку делать(Пока думаю о сортировки Шелла, но может есть по лучше)???
  • Вопрос задан
  • 879 просмотров
Подписаться 4 Оценить 2 комментария
Решения вопроса 1
longclaps
@longclaps
Кто ж знает, что ты там нарешал. По идее, нужно было бы по набору слов построить префиксное дерево, в каждом узле которого - однобуквенный префикс (в корне префикс не нужен), количество начинающихся с него и его родителей слов и ссылки (не более 26 - по числу букв алфавита) на дочерние узлы.
При вызовах нужно выбрать ветвь перфикса и отсортировать её дочерние узлы. Для столь коротких массивов актуальна сортировка вставкой (да-да), но если хочешь попонтоваться - выбери что-то еще.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы