Dado un array [a1b2c3d4] convertir a [abcd1234]

Question

restricciones:

1. O (1) espacio
2. O (n) Tiempo de

No es una pregunta tarea simplemente una pregunta interesante que encontré

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

Método 1

* Con O (n) de memoria *

• Divide la matriz en dos partes de forma recursiva. (siga dividiendo hasta el tamaño < = 2 para cada problema secundario)
• Primero ordene cada problema secundario con el conjunto y los números al final.
• fusionar los arrays de problemas sub

Método 2

En O (n log n) Tiempo de

• ordenar la matriz orden lexicográfico base se convierte en 1234abcd
• Invierta ambas mitades de la matriz 4321dcba
• Reverse toda la abcd1234 cadena

Método 3

Si se definió rango de números de

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

Método 4 Podemos utilizar Método 3 con HashMap si queremos eliminar la restricción de la gama de enteros, pero entonces necesitará 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 que aquí se refiere a:

Dada una secuencia de x1y1x2y2x3y3 .... XnYn donde x1, x2 son alfabetos x1 x2 < < .... < xn y Y1Y2 ... yn son enteros.y1 y2 < < .... < in Organizar la salida como X1X2 ... xny1y2 ... yn

¿Alguna sugerencia?

Answer 1

¿Qué es n? Suponiendo que n es el tamaño de la entrada:

Esto se denomina convolución de una lista. Básicamente, debe convertir una lista de pares (a,1),(b,2),(c,3),(d,4) en un par de listas (a,b,c,d),(1,2,3,4). Es la misma operación que la transposición de una matriz.

De todos modos, tienes que pensar en la estructura como una matriz k-dimensional, donde k = lg n. La convolución de la matriz es lo que obtienes cuando "mueves" el valor en un índice i para indexar i rotado en modo bit. En este caso, queremos rotar los índices hacia la derecha 1 bit. Esto significa que la convolución es una permutación con una longitud de ciclo máxima de k. El truco es seleccionar un índice de cada ciclo; esto siempre incluirá 0 y n-1.

EDITAR: En realidad, lo que probablemente quiera es descomponer la permutación en un producto de transposiciones. Entonces, todo lo que necesitas hacer es intercambios.

Answer 2

Aquí está mi algoritmo en O (n).

cycle_leader vacío (int * arr, int n) {

for (int i = 1; i < n/2; i+= 2) 
{ 
    int j = i; 
    int save; 
    int tmp = arr[i]; 

    do{ 
     if (j & 1) //odd index element 
      j = n/2 + j/2; 
     else 
      j = j/2; 

     save = arr[j]; 
     arr[j] = tmp; 
     tmp = save; 
    } while(j != i); 
} 

}

Answer 3

Solución:

1. Primera (índice 0) y la última (índice n-1) hacer no moverse.
2. Número total de movimientos es (n - 2)

3. Incluso los elementos numéricos en la fuente son alfabetos. Se mueven a la primera mitad.

   target = j/2 // n es incluso

4. elementos número impar en la fuente son números, y se mueven en el segundo medio.

   target = n/2 + piso (j/2)

5. A partir de 1 elemento, mueva que a su ubicación de destino.

6. Mueva lo que encuentre en la ubicación de destino a su destino y así sucesivamente hasta que se forme un bucle. Nota 1: A veces, el ciclo no incluye todos los elementos en la lista, , así que continúe con j + 2 Nota 2: A veces, al final de un bucle, se logrará la solución deseada, pero si continuamos , la matriz se revolverá nuevamente. Para solucionar esto, cuente la cantidad de movimientos que sucedieron y corte cuando llegue a n - 2.

puede intentar ejecutar el código, el clon y editar aquí Online Java Compiler IDE

---

int maxShifts = n - 2; // This is required to fix going around and messing up. 
int shifts = 0; 

for (int i = 1; i < n && shifts < maxShifts; i+=2) { 
    int source = i; 
    char itemToMove = array[source]; 
    do { 
    int target; 
    if (source % 2 == 0) { 
     target = source/2; // Even index is an alphabet 
    } else { 
     target = n/2 + source/2; // Odd index is a digit, that goes in the second half 
    } 
    char tmp = array[target]; 
    array[target] = itemToMove; 
    itemToMove = tmp; 

    shifts++; 
    source = target; 

    } while (i != source /*&& shifts < maxShifts*/); // Full cycle reached 

} 

Answer 4

O bien, puede utilizar el poderoso Python, y traducirla en java:

a = [1,'a',2,'b',3,'c',4,'d'] 
a = a[0:len(a):2] + a[1:len(a):2] 
print(a) #this will print [1,2,3,4,'a','b','c','d']