Java – Array rotante

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)

  • looping una volta da k index a (length-1)
  • 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 }