サーチ…


前書き

プログラミングを勉強する私の道では、練習問題として解決すべき単純で興味深い問題がありました。これらの問題の1つは、配列(または別のコレクション)を特定の値だけ回転させることでした。ここで私はそれを行う簡単な公式をあなたと共有します。

与えられたシフトで配列を回転させる一般的なメソッドの例

私は、シフト値が負であるときに左に回転し、値が正であるときに右に回転することを指摘したい。

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

このコードで重要なことは、回転後に新しいインデックス値が見つかる数式です。

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

それについてもう少し詳しく知りたいです:

(shiftCount%array.Length) - >シフト値を配列の長さに正規化します(長さ10の配列では、シフト1または11は同じものです。-1と-11についても同様です) 。

array.Length +(shiftCount%array.Length) - >これは左回転のために行われ、負のインデックスにはならず、配列の最後まで回転させます。インデックス0と回転-1の長さが10の配列では、負の数(-1)になり、実際の回転インデックスの値は9になりません。(10 +(-1%10)= 9)

index + array.Length +(shiftCount%array.Length) - >新しいインデックスを取得するために、インデックスにローテーションを適用するので、ここであまり言及しません。 (0 + 10 +(-1%10)= 9)

index + array.Length +(shiftCount%array.Length)%array.Length - > 2番目の正規化は、新しいインデックス値が配列の外側には出てこないことを確認していますが、配列の先頭に値を回転します。これは右回転のためです。なぜなら、長さ10の配列ではインデックス9がなく、回転1では配列の外側にあるインデックス10に入り、実際の回転インデックス値は0になりません。 + 10 +(1%10))%10 = 0)



Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow