Ограничения:

O (1) пробелВовремя

Это не домашнее задание, а интересный вопрос, с которым я столкнулся.

Вот некоторые решения, о которых я мог подумать, но ничего, что могло бы сделать это при данных ограничениях.

Способ 1

* С O (n) памятью *

Разделите массив на две части рекурсивно. (продолжайте делить до размера <= 2 для каждой подзадачи)Сортируйте каждую подзадачу с массивом первым и числами в конце.Слияние массивов подзадач

Способ 2

За O (n log n) время

Сортировать массив на основе лексикографического порядка становится 1234abcdОбратить обе половины массива 4321dcbaПеревернуть всю строку abcd1234

Способ 3

Если диапазон чисел был определен

Также, если дело в том, что числа находятся в определенном диапазоне, тогда я могу инициализировать int скажем track = 0; И установить соответствующий бит, когда я сталкиваюсь с числом в массиве, например (1 << а [2]). 1. Поменяйте местами алфавиты на первую половину массива. 2. Пометьте числа в переменной track. 3. Позже используйте track, чтобы заполнить вторую половину массива.

Способ 4 Мы можем использовать метод 3 с HashMap, если мы хотим удалить ограничение диапазона целых чисел, но тогда ему потребуется больше памяти.

Не могу придумать лучшего способа решения общей проблемы в O (1) времени и O (n) пространстве.

Общая проблема здесь относится к:

Дана последовательность x1y1x2y2x3y3 .... xnyn, где x1, x2 - алфавиты x1 < х2 <.... < xn и y1y2 ... yn - целые числа. у1 < у2 <.... < Упорядочить вывод как x1x2 ... xny1y2 ... yn

Какие-либо предложения ?