Restricciones:

O (1) espacioA tiempo

No es una pregunta de tarea, solo una pregunta interesante que encontré.

Aquí hay algunas soluciones que podría pensar, pero nada que lo haga en determinadas restricciones.

Método 1

* Con memoria O (n) *

Divide la matriz en dos partes recursivamente. (siga dividiendo hasta el tamaño <= 2 para cada subproblema)Ordena cada sub problema con la matriz primero y los números al final.Fusionar las matrices de sub problemas

Método 2

En tiempo O (n log n)

Ordenar el orden Lexicográfico basado en matrices que se convierte en 1234abcdInvertir ambas mitades de la matriz 4321dcbaInvertir toda la cadena abcd1234

Método 3

Si se definió rango de números

Además, si el caso fuera que los números están en un rango específico, entonces puedo inicializar una pista int say = 0; Y establezca el bit apropiado cuando me encuentre con un número en una matriz, por ejemplo (1 << a [2]). 1. Cambie los alfabetos a la primera mitad de la matriz 2. Marque los números en la variable de pista 3. luego use la pista para completar la segunda mitad de la matriz.

Método 4 Podemos usar el Método 3 con HashMap si queremos eliminar la restricción del rango de enteros, pero luego necesitaremos más memoria.

No se puede pensar en una mejor manera de resolver el problema genérico en O (1) tiempo y O (n) espacio.

Problema genérico aquí se refiere a:

Dada una secuencia x1y1x2y2x3y3 .... xnyn donde x1, x2 son alfabetos x1 <x2 <.... <xn y y1y2 ... yn son números enteros. y1 <y2 <.... <yn Organiza la salida como x1x2 ... xny1y2 ... yn

Alguna sugerencia ?