C#で配列をk回回転させる方法｜反転アルゴリズムによる実装を解説

配列と整数 k が与えられたとき、その配列を k 回回転させるのが本記事のテーマです。例えば k = 3 が指定された場合、配列は3回分だけ回転します。

ここで紹介するのは「反転アルゴリズム（Reversal Algorithm）」と呼ばれる定番手法です。配列全体を一度反転し、その後それぞれの区間を再度反転するだけで、追加メモリほぼゼロで効率的に回転を実現できます。

アルゴリズムの基本手順

まず、配列・開始インデックス・終了インデックスを引数として受け取る Reverse メソッドを作成します。このメソッドを活用し、次の3ステップで回転を行います。

• ステップ1： 配列全体（インデックス0 ～ 配列長-1）を反転する
• ステップ2： 先頭から k 番目まで（インデックス0 ～ k-1）を反転する
• ステップ3： 残りの部分（インデックスk ～ 配列長-1）を反転する

C#での実装例

using System;

namespace ConsoleApplication {
    public class Arrays {
        public void ReverseArrayKTimes(int[] arr, int k) {
            Reverse(arr, 0, arr.Length - 1);
            Reverse(arr, 0, k - 1);
            Reverse(arr, k, arr.Length - 1);
        }

        private void Reverse(int[] arr, int start, int end) {
            while (start < end) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                start++;
                end--;
            }
        }
    }

    class Program {
        static void Main(string[] args) {
            Arrays a = new Arrays();
            int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
            a.ReverseArrayKTimes(arr, 3);

            for (int i = 0; i < arr.Length; i++) {
                Console.WriteLine(arr[i]);
            }
            Console.ReadLine();
        }
    }
}

実行結果

3 2 1 9 8 7 6 5 4

処理の流れをステップごとに確認

サンプルコードでは、初期配列 { 9, 8, 7, 6, 5, 4, 3, 2, 1 } を k = 3 で回転しています。各ステップでの配列の状態は以下の通りです。

• 初期状態：9 8 7 6 5 4 3 2 1
• ステップ1（全体を反転）：1 2 3 4 5 6 7 8 9
• ステップ2（先頭3要素を反転）：3 2 1 4 5 6 7 8 9
• ステップ3（残りを反転）：3 2 1 9 8 7 6 5 4

計算量について

このアルゴリズムの時間計算量は O(n)、追加で必要な空間計算量は O(1) です。一時変数を使って要素を入れ替えるだけで済むため、新しい配列を確保してコピーする方法よりもメモリ効率に優れています。