Фон
Недавно я решил решить некоторые проблемы в leetcode.com для развлечения и практики моей java, которой я давно не пользовался. Я решил задокументировать свой мыслительный процесс по мере решения этих проблем. Вы можете найти некоторые другие решения в таблице серий над этим разделом.
Проблема
Сортировка по частоте Учитывая строку, верните другую строку, в которой символы отсортированы по частоте их появления с наибольшим количеством повторяющихся в начале. Напр.:
Input: tree Output: eert Input: aabbbc Output: bbbaac
Решение
Всякий раз, когда я вижу подобную проблему, когда результат зависит от того, как каждый элемент в списке связан с другим элементом в списке (здесь, например, сколько раз каждый элемент появляется в списке), мой разум немедленно переходит к двухпроходному подходу с хэш-картой.
Это не потому, что хэш-карты – моя любимая структура данных (у меня нет любимой структуры данных), а скорее из-за простоты поиска хэш-карт. Поэтому обычно мой разум думает о том, как я могу сохранить данные в хэш-карте на первом проходе, чтобы я мог просмотреть их на втором проходе, тем самым избегая вложенного цикла.
Эта проблема ничем не отличалась и я начинал точно так же. Но когда я начал записывать, какая хэш-карта мне нужна, я понял, что мне могут понадобиться две хэш-карты. Один для представления количества символов, а другой для представления самих различных подсчетов. (Возможно, есть лучший способ сделать это, но это то, что я придумал с первой попытки)
Итак, мои две хэш-карты для второго примера выше выглядели так в конце первого прохода:
// For each character a string with their frequency { a: aa, b: bbb, c: c } // For each count a list of characters with the count { 1: [a, b, c], 2: [a, b], 3: [b], }
Теперь на второй карте есть некоторое повторение, но это было нормально, так как я не хотел добавлять дополнительную сложность поиска в первом проходе.
Отсюда нужно было отсортировать подсчеты, а затем сформировать строку с другой карты.
Это привело к следующему коду:
Сложность
Поскольку здесь задействовано несколько разных шагов, давайте посмотрим на сложность каждого шага:
- Первый проход – построение хэш-карты –
O(n)
где n – длина строки. - Сортировка подсчетов –
O(k.log k)
где k – количество уникальных подсчетов. - Второй проход – построение результата – 3.1
O(n)
– если каждый персонаж появлялся только один раз. 3.2O(k + n)
– если естьk
считается, что каждый из них содержит более одного элемента. Но так как k < n, то это действительноO(n)
Так что самая дорогая операция здесь – это сортировка.
Оригинал: “https://dev.to/deepakvenkat/programming-exercise-frequency-sort-3k08”