Рубрики
Без рубрики

Упражнение по программированию: Сортировка по частоте

Сортировка по частоте. С пометкой java, программирование, leetcode.

Фон

Недавно я решил решить некоторые проблемы в 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],
}

Теперь на второй карте есть некоторое повторение, но это было нормально, так как я не хотел добавлять дополнительную сложность поиска в первом проходе.

Отсюда нужно было отсортировать подсчеты, а затем сформировать строку с другой карты.

Это привело к следующему коду:

Сложность

Поскольку здесь задействовано несколько разных шагов, давайте посмотрим на сложность каждого шага:

  1. Первый проход – построение хэш-карты – O(n) где n – длина строки.
  2. Сортировка подсчетов – O(k.log k) где k – количество уникальных подсчетов.
  3. Второй проход – построение результата – 3.1 O(n) – если каждый персонаж появлялся только один раз. 3.2 O(k + n) – если есть k считается, что каждый из них содержит более одного элемента. Но так как k < n, то это действительно O(n)

Так что самая дорогая операция здесь – это сортировка.

Оригинал: “https://dev.to/deepakvenkat/programming-exercise-frequency-sort-3k08”