Dato un array [a1b2c3d4] convertire in [abcd1234]

Question

Vincoli:

1. O (1) spazio
2. O (n) Tempo

E non è una questione compiti a casa solo una domanda interessante che ho trovato.

Ecco alcune soluzioni che potrei pensare, ma nulla che lo faccia in termini di vincoli.

Metodo 1

* Con O (n) * memoria

• Dividere la matrice in due parti in modo ricorsivo. (continuare a dividere fino alla dimensione < = 2 per ciascun sottotema)
• Ordinare ciascun sottotema con l'array prima e i numeri alla fine.
• unione sub problema matrici

Metodo 2

In O (n log n)

• ordinare l'array ordine lessicografico basato diventa 1234abcd
• Invertire entrambe le metà dell'array 4321dcba
• inverso l'intera stringa abcd1234

Metodo 3

Se è stato definito intervallo di numeri

Anche se il caso è che i numeri sono in un intervallo specifico allora posso inizializzare un int dì traccia = 0; E impostare il bit appropriato quando mi imbatto in un numero nell'array ad es. (1 < < a [2]). 1. Scambiare gli alfabeti nella prima metà dell'array 2. Contrassegnare i numeri nella variabile di traccia 3. Successivamente utilizzare la traccia per riempire la seconda metà dell'array.

Metodo 4 Siamo in grado di utilizzare il metodo 3 con HashMap se vogliamo rimuovere il vincolo della gamma di numeri interi, ma poi avrà bisogno di più memoria.

Non riesco a pensare ad un modo migliore per risolvere il problema generico in O (1) tempo e O (n) spazio.

Problema generico qui si riferisce a:

Data una sequenza di x1y1x2y2x3y3 .... XnYn dove x1, x2 sono alfabeti x1 < x2 < .... < xn e y1y2 ... yn sono interi.y1 y2 < < .... < yn Disporre l'output come x1x2 ... xny1y2 ... yn

Qualche suggerimento?

Answer 1

Che cos'è n? Supponendo che n è la dimensione dell'input:

Questa è chiamata la convoluzione di una lista. In sostanza, è necessario convertire un elenco di coppie in un paio di elenchi (a,b,c,d),(1,2,3,4). È la stessa operazione della trasposizione di una matrice.

In ogni caso, si deve pensare alla struttura come a un array k-dimensionale, dove k = lg n. La convoluzione dell'array è ciò che ottieni quando "sposti" il valore su un indice i per indicizzare ruotato a bit. In questo caso, vogliamo ruotare gli indici verso destra di 1 bit. Ciò significa che la convoluzione è una permutazione con una lunghezza massima del ciclo di k. Il trucco è quindi selezionare un indice per ogni ciclo - questo includerà sempre 0 e n-1.

MODIFICA: In realtà, ciò che si desidera è decomporre la permutazione in un prodotto di trasposizioni. Quindi, tutto ciò che devi fare è scambiare.

Answer 2

Ecco il mio algoritmo in O (n).

cycle_leader void (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

Soluzione:

1. First (indice 0) e l'ultimo (indice n-1) do non muoverti.
2. Il numero totale di spostamenti è (n - 2)

3. Anche gli elementi numerici nella sorgente sono alfabeti. Si spostano nel primo tempo.

   target = j/2 // n è anche

4. elementi numero dispari nell'origine sono numeri, e si muovono nella seconda metà.

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

5. A partire dal 1 ° elemento, spostare che per la sua posizione di destinazione.

6. Sposta quello che si trova nella posizione di destinazione a destinazione e così via fino a formare un anello. Nota 1: A volte, il ciclo non include tutti gli elementi della lista, così, continuare con j + 2 Nota 2: A volte, alla fine di un ciclo, sarà raggiunto la soluzione desiderata, ma se continuiamo , l'array verrà nuovamente criptato. Per risolvere il problema, conta il numero di movimenti verificatisi e taglia quando raggiunge n - 2.

È possibile provare a eseguire il codice, clonare e modificare qui 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

In alternativa, è possibile utilizzare il potente Python, e tradurlo in 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']