C# Language
O (n) Algorytm rotacji kołowej tablicy

Wprowadzenie

Przykład ogólnej metody, która obraca tablicę o dane przesunięcie

Chciałbym zaznaczyć, że obracamy w lewo, gdy wartość przesunięcia jest ujemna, i obracamy w prawo, gdy wartość jest dodatnia.

    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;
    }

W tym kodzie istotna jest formuła, w której po obrocie znajdujemy nową wartość indeksu.

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

Oto trochę więcej informacji na ten temat:

(shiftCount% array.Length) -> normalizujemy wartość przesunięcia, aby była długością tablicy (ponieważ w tablicy o długości 10 przesunięcie 1 lub 11 jest tym samym, to samo dotyczy -1 i -11) .

array.Length + (shiftCount% array.Length) -> odbywa się to z powodu rotacji w lewo, aby upewnić się, że nie przejdziemy do indeksu ujemnego, ale obrócimy go do końca tablicy. Bez niego dla tablicy o długości 10 dla indeksu 0 i obrotu -1 przechodzilibyśmy do liczby ujemnej (-1) i nie otrzymywalibyśmy rzeczywistej wartości indeksu obrotu, która wynosi 9. (10 + (-1% 10) = 9)

index + array.Length + (shiftCount% array.Length) -> niewiele do powiedzenia tutaj, ponieważ stosujemy obrót do indeksu, aby uzyskać nowy indeks. (0 + 10 + (-1% 10) = 9)

index + array.Length + (shiftCount% array.Length)% array.Length -> druga normalizacja upewnia się, że nowa wartość indeksu nie wychodzi poza tablicę, ale obraca wartość na początku tablicy. Odnosi się do rotacji w prawo, ponieważ w tablicy o długości 10 bez niej dla indeksu 9 i rotacji 1 przechodzilibyśmy do indeksu 10, który znajduje się poza tablicą, i nie otrzymujemy rzeczywistej wartości indeksu obrotu wynoszącej 0. ((9 + 10 + (1% 10))% 10 = 0)