Quindi l’objective è quello di ruotare gli elementi in un array giusto a
volta. Come esempio; se a==2
, quindi array = {0,1,2,3,4}
diventerebbe array = {3,4,0,1,2}
Ecco cosa ho:
for (int x = 0; x <= array.length-1; x++){ array[x+a] = array[x]; }
Tuttavia, questo non tiene conto di quando [x+a]
è maggiore della lunghezza dell’array. Ho letto che dovrei memorizzare quelli che sono maggiori in un Array diverso, ma visto come a
variabile non sono sicuro che sia la soluzione migliore. Grazie in anticipo.
Aggiungi una lunghezza dell’array modulo al tuo codice:
// create a newArray before of the same size as array // copy for(int x = 0; x <= array.length-1; x++){ newArray[(x+a) % array.length ] = array[x]; }
Dovresti anche creare una nuova Array
da copiare, in modo da non sovrascrivere i valori, che ti serviranno in seguito.
Nel caso in cui non si voglia reinventare la ruota (forse è un esercizio ma può essere utile sapere), è ansible utilizzare Collections.rotate
.
Si noti che richiede una matrice di oggetti, non un tipo di dati primitivo (altrimenti si scambieranno gli array stessi nell’elenco).
Integer[] arr = {0,1,2,3,4}; Collections.rotate(Arrays.asList(arr), 2); System.out.println(Arrays.toString(arr)); //[3, 4, 0, 1, 2]
Arraycopy è un’operazione costosa, sia in termini di tempo che di memoria. Questo sarebbe un modo efficace per ruotare l’array senza utilizzare spazio extra come la risposta accettata.
public void rotate(int[] nums, int k) { // k = 2 k %= nums.length; // {0,1,2,3,4} reverse(nums, 0, nums.length - 1); // Reverse the whole Array // {4,3,2,1,0} reverse(nums, 0, k - 1); // Reverse first part (4,3 -> 3,4) // {3,4,2,1,0} reverse(nums, k, nums.length - 1); //Reverse second part (2,1,0 -> 0,1,2) // {3,4,0,1,2} } public void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } }
Un altro modo è copiare con System.arraycopy .
int[] temp = new int[array.length]; System.arraycopy(array, 0, temp, a, array.length - a); System.arraycopy(array, array.length-a, temp, 0, a);
Penso che il modo più veloce sarebbe utilizzare System.arrayCopy () che è il metodo nativo:
int[] tmp = new int[a]; System.arraycopy(array, array.length - a, tmp, 0, a); System.arraycopy(array, 0, array, a, array.length - a); System.arraycopy(tmp, 0, array, 0, a);
Riutilizza anche l’array esistente. Potrebbe essere utile in alcuni casi. E l’ultimo vantaggio è che la dimensione della matrice temporanea è inferiore alla matrice originale. In questo modo è ansible ridurre l’utilizzo della memoria quando è piccolo.
Soluzione Java racchiusa in un metodo:
public static int[] rotate(final int[] array, final int rIndex) { if (array == null || array.length <= 1) { return new int[0]; } final int[] result = new int[array.length]; final int arrayLength = array.length; for (int i = 0; i < arrayLength; i++) { int nIndex = (i + rIndex) % arrayLength; result[nIndex] = array[i]; } return result; }
Per Left Rotate è molto semplice
Prendi la differenza tra la lunghezza dell’array e il numero di posizioni da spostare.
Per esempio
int k = 2; int n = 5; int diff = n - k; int[] array = {1, 2, 3, 4, 5}; int[] result = new int[array.length]; System.arraycopy(array, 0, result, diff, k); System.arraycopy(array, k, result, 0, diff);
// stampa l’output
Domanda: https://www.hackerrank.com/challenges/ctci-array-left-rotation
Soluzione: Ecco come ho provato il metodo arrayLeftRotation con la complessità o (n)
2a volta per 0 a kth indice
public static int [] arrayLeftRotation (int [] a, int n, int k) {
int [] resultArray = new int [n];
int arrayIndex = 0;
// i primi indici nk verranno popolati in questo ciclo
for (int i = k; i resultArray [arrayIndex] = a [i];
arrayIndex ++;
}
// I secondi indici k verranno popolati in questo ciclo
for (int j = arrayIndex; j <(arrayIndex + k); j ++) {
resultArray [j] = a [J (nk)];
}
return resultArray;
}
package com.array.orderstatistics; import java.util.Scanner; public class ArrayRotation { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int r = scan.nextInt(); int[] a = new int[n]; int[] b = new int[n]; for (int i = 0; i < n; i++) { a[i] = scan.nextInt(); } scan.close(); if (r % n == 0) { printOriginalArray(a); } else { r = r % n; for (int i = 0; i < n; i++) { b[i] = a[(i + r) < n ? (i + r) : ((i + r) - n)]; System.out.print(b[i] + " "); } } } private static void printOriginalArray(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } }
In ruby, la rotazione di un array può essere ansible in una sola riga.
def array_rotate(arr) i, j = arr.length - 1, 0 arr[j],arr[i], i, j = arr[i], arr[j], i - 1, j + 1 while(j
Domanda: ruota l’array data una distanza specifica. Metodo 1: trasforma l’array int in ArrayList. Quindi utilizzare Collections.rotate (elenco, distanza).
class test1 { public static void main(String[] args) { int[] a = { 1, 2, 3, 4, 5, 6 }; List list = Arrays.stream(a).boxed().collect(Collectors.toList()); Collections.rotate(list, 3); System.out.println(list);//[4, 5, 6, 1, 2, 3] }// main }