Originariamente inviata da
sophkant
se per esempio decido di fare uno shift di 3 posizioni e il vettore e' di [6], gli ultimi 3 elementi del vettore vengono shiftati correttamente di 3 posizioni. i primi 3 invece non risultano shiftati e viene riportato nel print questo numero: -858993460
Stai sforando l'array in lettura: immagina di avere un array di N=10 elementi e dover shiftare di 5 posizioni; con i >= 5 vai a leggere da oltre la fine dell'array.
Per far funzionare un approccio di questo tipo dovresti come minimo fare il lookup in modulo (ovvero, (i + posizioni) % N), in modo che quando vai a leggere oltre la fine dell'array di fatto ricominci da capo. Tuttavia, anche questo sistema non funziona, perché quando ricominci a leggere dall'inizio stai rileggendo elementi che hai già sovrascritto. Una soluzione semplice può essere fare una copia dell'array originale e usare quella come input:
codice:
int rotate(int arr[], int N, int places) {
int *copy = malloc(N*sizeof(*arr));
places = (places + N) % N; // riconduce sia rotazione a destra che a sinistra ad una rotazione a sinistra
for(int i = 0; i < N; ++i) copy[i] = arr[i];
for(int i = 0; i < N; ++i) arr[i] = copy[(i + places + N) % N];
free(copy);
}
Questa soluzione è O(N) in tempo e O(N) in spazio. Con poco più sforzo si può renderla O(N) in tempo e O(places) in spazio, copiando solo gli elementi che ci servono:
codice:
int rotate(int arr[], int N, int places) {
places = (places + N) % N; // riconduce sia rotazione a destra che a sinistra ad una rotazione a sinistra
int *copy = malloc(places*sizeof(*arr));
for(int i = 0; i < places; ++i) copy[i] = arr[i];
for(int i = 0; i < N; ++i) {
int srcIdx = (i + places + N) % N;
if(srcIdx < i) arr[i] = copy[srcIdx];
else arr[i] = arr[srcIdx];
}
free(copy);
}
Viceversa, la soluzione proposta da oregon è O(N*places) in tempo, ma O(1) in spazio (non serve storage aggiuntivo).
Va detto però che esiste una soluzione ottimale O(N) in tempo e O(1) in spazio, prova a pensarci...