C# Language
O (n) Algorithmus für die Kreisrotation eines Arrays

Einführung

Beispiel für eine generische Methode, mit der ein Array um eine bestimmte Schicht gedreht wird

Ich möchte darauf hinweisen, dass wir uns nach links drehen, wenn der Verschiebungswert negativ ist, und wir nach rechts drehen, wenn der Wert positiv ist.

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

Wichtig in diesem Code ist die Formel, mit der wir nach der Drehung den neuen Indexwert finden.

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

Hier ein wenig mehr Informationen dazu:

(shiftCount% array.Length) -> Wir normalisieren den Verschiebungswert so, dass er in der Länge des Arrays liegt (da in einem Array mit der Länge 10 die Verschiebung von 1 oder 11 dasselbe ist, gilt dasselbe für -1 und -11) .

array.Length + (shiftCount% array.Length) -> Dies geschieht aufgrund von Linksrotationen , um sicherzustellen, dass wir nicht in einen negativen Index gehen, sondern bis zum Ende des Arrays drehen. Ohne ein Array mit der Länge 10 für Index 0 und einer Rotation -1 würden wir in eine negative Zahl (-1) gehen und nicht den realen Rotationsindexwert erhalten, der 9 ist. (10 + (-1% 10) = 9)

index + array.Length + (shiftCount% array.Length) -> nicht viel zu sagen, da wir die Drehung auf den Index anwenden, um den neuen Index zu erhalten. (0 + 10 + (-1% 10) = 9)

index + array.Length + (shiftCount% array.Length)% array.Length -> Die zweite Normalisierung stellt sicher, dass der neue Indexwert nicht außerhalb des Arrays liegt, sondern den Wert am Anfang des Arrays dreht. Es ist für Rechtsdrehungen, da in einem Array mit der Länge 10 ohne Index 9 und einer Rotation 1 der Index 10 außerhalb des Arrays aufgerufen würde und der Indexwert der realen Rotation nicht 0 ist ((9) + 10 + (1% 10)) 10 = 0)