Ограничения:
- O (1) пространство
- O (n) Время
Это не вопрос домашней работы, а интересный вопрос, который я встретил.
Вот некоторые решения, о которых я мог думать, но ничего не делает в заданных ограничениях.
Метод 1
* С памятью O (n) *
- Разделите массив на две части рекурсивно. (продолжайте делить до размера <= 2 для каждой дополнительной проблемы).
- Сортируйте каждую вспомогательную проблему с первым массивом и номерами в конце.
- Объединить массивы вспомогательных задач
Метод 2
В O (n log n) время
- Сортировка массива на основе лексикографического порядка составляет 1234abcd
- Обратить обе половины массива 4321dcba
- Обратить всю строку abcd1234
Метод 3
Если был определен диапазон чисел
Также, если дело было в том, что числа находятся в определенном диапазоне, тогда я могу инициализировать int say track = 0; И установите соответствующий бит, когда я сталкиваюсь с числом в массиве например (1 < a [2]). 1. Обмен алфавитами в первую половину массива 2. Отметьте числа в переменной дорожки 3. позже используйте дорожку для заполнения второй половины массива.
Метод 4 Мы можем использовать метод 3 с HashMap, если мы хотим удалить ограничение диапазона целых чисел, но тогда ему потребуется больше памяти.
Невозможно представить лучший способ решить общую проблему в O (1) и O (n) пространстве.
Общая проблема здесь относится к:
Учитывая последовательность x1y1x2y2x3y3.... xnyn где x1, x2 - алфавиты x1 < x2 < хп и y1y2... yn - целые числа. y1 < y2 < уп Расположите выход как x1x2... xny1y2... yn
Любые предложения?