配列の左回転をO(n)時間・O(1)空間で実現するC++プログラムの書き方

本記事では、サイズnの整数配列と複数の回転位置kが与えられたとき、指定されたインデックスkから配列を左方向へ回転させた結果を出力する方法を、時間計算量O(n)・空間計算量O(1)の制約のもとで解説します。

配列の左回転とは、各要素を左へk個分ずらし、はみ出した要素を右端に折り返して配置する操作です。例えば、配列 {1, 2, 3, 4, 5} を1回左に回転すると {2, 3, 4, 5, 1} になります。

この手法の鍵となるのは剰余演算（%）です。回転後の配列を新たに作成することなく、インデックス計算だけで結果を直接出力できるため、追加のメモリ領域を一切必要としません。

入力例と出力例

Input: arr[] = {1, 2, 3, 4, 5}
    K1 = 1
    K2 = 3
    K3 = 6
Output:
    2 3 4 5 1  （1回左回転）
    4 5 1 2 3  （3回左回転）
    2 3 4 5 1  （6回左回転）

K3 = 6 のケースに注目してください。配列の長さは5なので、6回の回転は「5回で元に戻り、さらに1回回転する」ことと同じ結果になります。つまりk % n（kを配列サイズnで割った余り）を求めれば実質的な回転回数がわかるため、kがnより大きい場合でも正しく処理できます。

アルゴリズムの手順

START
Step 1 -> 関数 void leftRotate(int arr[], int n, int k) を定義する
    int cal = k % n を宣言（実質的な回転回数を計算）
    Loop For int i=0 and i<n and i++
        arr[(cal+i)%n] を出力
    End
Step 2 -> main() 内での処理
    配列 a[]={ 1,2,3,4} を宣言
    int size=sizeof(a)/sizeof(a[0]) を宣言（要素数を取得）
    int k=1 として leftRotate(a, size, k) を呼び出す
    k=2 として leftRotate(a, size, k) を呼び出す
    k=3 として leftRotate(a, size, k) を呼び出す
STOP

計算量のポイント

このアルゴリズムの核心は、インデックス変換式 (cal + i) % n にあります。回転後の配列におけるi番目の要素は、元の配列では (cal + i) % n 番目に存在します。この式を利用すれば、配列そのものを書き換えることなく、1周のループで回転後の並び順を順番に出力できます。

• 時間計算量：O(n) — 配列の各要素をちょうど1回ずつ訪問するため
• 空間計算量：O(1) — 一時配列などの追加メモリを一切使用しないため

C++による実装コード

#include <bits/stdc++.h>
using namespace std;
void leftRotate(int arr[], int n, int k){
    int cal = k % n; // 実質的な回転回数を計算
    for (int i = 0; i < n; i++)
        cout << (arr[(cal + i) % n]) << " "; // 回転後の位置に対応する要素を出力
    cout << "\n";
}
int main(){
    int a[] = { 1,2,3,4};
    int size = sizeof(a) / sizeof(a[0]); // 配列の要素数を求める
    int k = 1;
    leftRotate(a, size, k); // 1回左回転
    k = 2;
    leftRotate(a, size, k); // 2回左回転
    k = 3;
    leftRotate(a, size, k); // 3回左回転
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

2 3 4 1
3 4 1 2
4 1 2 3

このように、剰余演算を活用したインデックス計算により、配列を実際に書き換えることなく左回転の結果を効率的に出力できます。大きな配列や複数の回転クエリを扱う場面で特に有効なテクニックなので、ぜひ覚えておきましょう。