TL;DR

  • Проблемы, в которых вы считаете частоты, часто являются отличными кандидатами на использование структуры данных карты.
  • Нам нужно подсчитать частоты символов, экстраполировать символы, отсортировать экстраполированные строки, а затем снова соединить эти строки вместе.
  • Этот алгоритм имеет O(n*log(n) временную сложность и O(n) пространственную сложность.

описание проблемы

Данная строка s отсортирована в порядке убывания частоты встречаемости символов. Частота символа — это количество раз, которое он появляется в строке.

Вернуть отсортированную строку. Если ответов несколько, верните любой из них.

Эта проблема исходит от LeetCode. Там нет недостатка в практических задачах, но LeetCode — одна из самых популярных платформ для оттачивания ваших навыков проектирования алгоритмов. Благодаря практическим проблемам, решениям и здоровой пользовательской базе для обсуждения проблем LeetCode является отличным ресурсом.

Решение проблемы

Ключом к решению этой проблемы является сопоставление символов с частотой их появления в строке. Всякий раз, когда вы сталкиваетесь с проблемой, в которой используется слово «частота», есть большая вероятность, что карта будет правильным инструментом для работы.

Как только все символы сопоставлены, нам нужно экстраполировать отдельные символы в строки, содержащие символ, повторяющийся нужное количество раз. Затем мы можем отсортировать эти строки и соединить их в одну окончательную строку.

Давайте разобьем логику на более мелкие, удобоваримые части.

Подсчет символов

Вместо того, чтобы пытаться неэффективно группировать и сортировать эти символы на месте, гораздо проще просто подсчитать частоту появления символов, а затем создать группы символов, которые мы хотели бы видеть позже. Структура данных карты особенно полезна здесь, потому что она реализована таким образом, что позволяет нам иметь постоянный поиск во времени (т.е. O(1)). Таким образом, используя карту, когда мы хотим добавить к подсчету персонажа, можно быстро проверить, есть ли у нас уже этот персонаж на карте.

Итак, мы можем пройтись по нашим персонажам и проверить, существуют ли они уже на нашей карте. Если они это сделают, мы увеличим счет для этого персонажа на 1, а если нет, мы добавим этого персонажа на карту с начальным значением счета 1.

Экстраполяция и сортировка

Экстраполяция символа в строку, состоящую из символа, повторяющегося с определенной частотой, может быть отдельным разделом этого алгоритма, но большинство зрелых языков программирования имеют встроенный декларативный способ сделать это. В JavaScript для этого мы можем использовать String.prototype.repeat.

С логикой экстраполяции уже позаботились, наша логика выглядит следующим образом: итерация по карте, экстраполяция символа и вставка этой экстраполированной строки в сортируемую структуру данных, а затем сортировка. Ключевым моментом здесь является использование легко сортируемой структуры данных. В JavaScript у массивов есть собственный метод Array.prototype.sort, который можно использовать для декларативной сортировки элементов, поэтому мы будем использовать его для хранения наших экстраполированных строк.

Присоединение

После того, как мы отсортировали наши строки, нам просто нужно соединить их вместе в нашу окончательную результирующую строку. Опять же, в JavaScript есть декларативный метод-прототип под названием Array.prototype.join, который сделает это за нас. Если вы предпочитаете реализовать логику объединения самостоятельно, вам просто нужно выполнить итерацию по массиву и объединить каждую строку в результирующую строку.

Реализация JavaScript

Теперь, когда у нас есть ментальная модель и алгоритм, перевести их в код довольно просто. Давайте посмотрим на реализацию JavaScript.

Как вы можете видеть, логика сопоставления реализована в строках со 2 по 7. Мы создаем пустой объект, который действует как наша карта, используем цикл for для итерации по нашей строке, и на каждой итерации мы используем базовое назначение свойств объекта для обновления частоты нашего характера.

Экстраполяция символов происходит в строках с 9 по 14. Вы заметите, что мы используем цикл for...in для итерации по нашему объекту, и на каждой итерации мы экстраполируем нашу строку, используя метод String.prototype.repeat, и помещаем ее в конец нашего массива. После этого мы используем Array.prototype.sort для сортировки строк по длине.

Наконец, мы используем Array.prototype.join, чтобы объединить наш массив строк в одну окончательную строку в строке 17.

Если вы хотите запустить этот код, вы можете скопировать его отсюда.

Эффективность

Алгоритм хорош настолько, насколько хороша его эффективность. Неэффективный алгоритм, безусловно, лучше, чем ничего во время интервью, но, как правило, подход «грубой силы» не поможет. Поэтому важно понимать, как рассчитать эффективность вашего алгоритма и как передать эту информацию другим.

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

Сложность времени

Для нашей задачи отображение является линейным (то есть O(n)), как и соединение, но узким местом здесь является сортировка. Эффективность сортировки зависит от реализации среды выполнения JavaScript. Chrome использует движок V8, который сам реализует Array.prototype.sort с использованием алгоритма Timsort, который в среднем дает временную сложность O(n*log(n)). Поскольку эти операции являются последовательными и не вложенными, самая большая сложность затмевает другие, поскольку n (количество элементов в структуре данных) приближается к бесконечности.

Космическая сложность

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

Заключение

Проблемы с алгоритмами связаны с распознаванием того, когда использовать определенные логические шаблоны. Для этого вам необходимо ознакомиться с различными шаблонами и комбинациями шаблонов.

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

Первоначально опубликовано на https://codingbootcampguides.com.

Дополнительные материалы на plainenglish.io