Отсортируйте строку в соответствии со значениями символов ASCII.
Учитывая строку S размера N , задача состоит в том, чтобы отсортировать строку на основе их значений ASCII.
Примеры:
Input: S = “Geeks7”
Output: 7Geeks
Explanation: According to the ASCII values, integers comes first, then capital alphabets and the small alphabets.Input: S = “GeeksForGeeks”
Output: FGGeeeekkorss
Подход: Идея решения этой проблемы состоит в том, чтобы поддерживать массив для хранения частоты каждого символа, а затем добавлять их соответствующим образом в результирующую строку. Так как максимальное количество символов 256 , что делает сложность пространства постоянной. Выполните следующие шаги, чтобы решить эту проблему:
- Инициализируйте вектор freq[] размера 256 со значениями 0 для хранения частоты каждого символа строки.
- Переберите диапазон [0, N), используя переменную i , и увеличьте количество s[i] в массиве freq[] на 1 .
- Сделайте строку S пустой строкой.
- Перебрать диапазон [0, N), используя переменную i , и перебрать диапазон [0, freq[i]) , используя переменную j и добавив символ, соответствующий i-му значению ASCII в строке s[].
- После выполнения вышеуказанных действий выведите в качестве результата строку S.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(256*N)
Вспомогательное пространство: O(256)
Альтернативный подход: данная проблема также может быть решена с помощью функции сравнения со встроенной функцией sort() для сортировки данной строки в соответствии с их значениями ASCII.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N * log N)
Вспомогательное пространство: O(1)