C++で反転アルゴリズムを使って配列を回転する方法を解説

本記事では、与えられた配列をd要素だけ回転させる問題を、反転アルゴリズム（Reversal Algorithm）を用いて解く方法を詳しく解説します。まず、次のような入出力を想定してみましょう。

入力 : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2
出力 : arr[] = [3, 4, 5, 6, 7, 1, 2]
説明 : 配列を d = 2 だけ左方向に回転させます。ポイントは、この操作を「反転」のテクニックだけで実現することです。

反転テクニックによる配列の回転について検討した結果、次の3つのステップで目的を達成できることがわかります。

• ステップ1： まず、配列の先頭からd個の要素を反転します。
• ステップ2： 次に、残りの要素を反転します。
• ステップ3： 最後に、配列全体を反転します。

これら3つのステップを順に適用することで、d要素分回転された配列を得ることができます。

解法のアプローチ

この問題では、まず要素を反転させるための関数を作成します。その関数を利用して、上記の手順を順番に実行していくのが基本的な流れです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

void reverseArray(int arr[], int start, int end) { // 反転アルゴリズム
   while (start < end) { // start と end が一致したらループを抜ける
      int temp = arr[start];
      arr[start] = arr[end];
      arr[end] = temp;
      start++;
      end--;
   }
   return ;
}
void Rotate(int arr[], int d, int n) { // 回転関数
   if (d == 0) // 回転が不要な場合
      return;
   d = d % n; // d が n になると配列は元に戻るため剰余を取る
   reverseArray(arr, 0, d - 1); // 先頭のd要素を反転
   reverseArray(arr, d, n - 1); // 残りの要素を反転
   reverseArray(arr, 0, n - 1); // 配列全体を反転

   return ;
}
int main() {
   int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // 与えられた配列
   int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
   int d = 2;
   Rotate(arr, d, n);
   for(int i = 0; i < n; i++) // 配列の出力
      cout << arr[i] << " ";
   cout << "\n";
   return 0;
}

出力結果

3 4 5 6 7 1 2

コードの解説

上記のアプローチでは、最初にreverseArray関数を作成しています。この関数は「配列」「開始インデックス」「終了インデックス」の3つの引数を受け取り、指定された範囲の要素を両端から順に交換しながら反転させます。

続いてRotate関数の中で、先ほど設計したアルゴリズムを適用します。まず先頭のd要素を反転し、次に残りの要素を反転し、最後に配列全体を反転することで、配列がちょうどd要素分回転されます。

また、Rotate関数内で d = d % n という処理を行っています。これは、配列のサイズnと同じ回数だけ回転すると配列が元の状態に戻るため、無駄な計算を避ける目的があります。例えば、n = 7 の配列を d = 9 だけ回転させる場合、結果は d = 2 の回転と同一になるため、あらかじめ剰余を取っておくのが効率的です。

計算量について

このアルゴリズムの時間計算量は O(n)、必要な追加メモリは O(1) です。一時配列を使う別の手法（O(d)の追加メモリが必要）と比較して、メモリ効率に優れている点が大きな特徴といえます。

まとめ

本記事では、反転アルゴリズムを用いた配列の回転問題について解説しました。「先頭のd要素を反転 → 残りの要素を反転 → 全体を反転」という3段階の操作により、追加メモリをほとんど使わずに配列を効率的に回転できます。同じロジックはC、Java、Pythonなど他の言語でも同様に実装可能です。競技プログラミングや技術面接でも頻出のテクニックなので、ぜひマスターしておきましょう。