Constraints :

O(1) space O(n) Time

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

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

Method 1

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

Divide the array in two parts recursively. ( keep dividing till the size <=2 for each sub problem ) Sort each sub problem with array first and numbers at end. Merge the sub problem arrays

Method 2

In O(n log n) time

Sort the array based Lexicographical order it becomes 1234abcd Reverse both halves of array 4321dcba Reverse the whole string abcd1234

Method 3

If range of numbers was defined

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

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

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

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

Дана последовательность x1y1x2y2x3y3 .... xnyn         где x1, x2 - алфавиты x1 & lt; x2 & lt; .... & lt; хп         и y1y2 ... yn - целые числа. y1 & lt; y2 & lt; .... & lt; уп Организовать вывод как x1x2 ... xny1y2 ... yn

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