C# Language
O (n) Algoritmo per la rotazione circolare di un array

introduzione

Esempio di un metodo generico che ruota un array per un dato turno

Vorrei sottolineare che ruotiamo a sinistra quando il valore di spostamento è negativo e ruotiamo a destra quando il valore è positivo.

    public static void Main()
    {
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int shiftCount = 1;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]

        array = new []{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = 15;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]

        array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = -1;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]

        array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = -35;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]
    }

    private static void Rotate<T>(ref T[] array, int shiftCount)
    {
        T[] backupArray= new T[array.Length];

        for (int index = 0; index < array.Length; index++)
        {
            backupArray[(index + array.Length + shiftCount % array.Length) % array.Length] = array[index];
        }

        array = backupArray;
    }

La cosa importante in questo codice è la formula con cui troviamo il nuovo valore di indice dopo la rotazione.

(index + array.Length + shiftCount% array.Length)% array.Length

Ecco alcune informazioni in più:

(shiftCount% array.Length) -> normalizziamo il valore di spostamento in modo che sia nella lunghezza dell'array (poiché in un array con lunghezza 10, lo spostamento 1 o 11 è la stessa cosa, lo stesso vale per -1 e -11) .

array.Length + (shiftCount% array.Length) -> questo viene fatto a causa delle rotazioni a sinistra per assicurarsi che non entriamo in un indice negativo, ma ruotarlo fino alla fine dell'array. Senza di esso per una matrice di lunghezza 10 per l'indice 0 e una rotazione -1 dovremmo inserire un numero negativo (-1) e non ottenere il valore dell'indice di rotazione reale, che è 9. (10 + (-1% 10) = 9)

index + array.Length + (shiftCount% array.Length) -> Non c'è molto da dire qui quando applichiamo la rotazione all'indice per ottenere il nuovo indice. (0 + 10 + (-1% 10) = 9)

index + array.Length + (shiftCount% array.Length)% array.Length -> la seconda normalizzazione si sta accertando che il nuovo valore di indice non vada fuori dalla matrice, ma ruoti il ​​valore all'inizio dell'array. È per le giuste rotazioni, poiché in un array con lunghezza 10 senza esso per l'indice 9 e una rotazione 1 dovremmo andare nell'indice 10, che è al di fuori dell'array, e non ottenere il valore dell'indice di rotazione reale è 0. ((9 + 10 + (1% 10))% 10 = 0)