C++で配列を右にk要素回転！反転アルゴリズムの仕組みと実装を徹底解説

この記事では、与えられた配列を右方向にk要素だけ回転させるための「反転アルゴリズム（Reversal Algorithm）」について詳しく解説します。

入力 : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
出力 : { 43, 7, 3, 7, 4, 6, 2, 6 }
説明 : 配列の各要素を右に4つ移動させると { 43, 7, 3, 7, 4, 6, 2, 6 } になります。

入力 : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
出力 : { 4, 9, 3, 8, 5, 8, 2, 1 }

解決策へのアプローチ

最も直感的な方法は、各要素を1つずつ右にシフトする操作をk回繰り返すことです。しかし、この方法は時間計算量が O(k × N) となるため、配列のサイズやkが大きい場合には非効率になってしまいます。

そこで有効なのが反転アルゴリズムです。配列の回転は、特定の範囲を反転（逆順に並べ替え）する操作の組み合わせによって実現できます。具体的な手順は以下の通りです。

• まず、配列全体を反転します。
• kがN（配列のサイズ）より大きい場合に備えて、k を k % N に置き換えます。
• 先頭からk番目までの要素を反転して、正しい順序に戻します。
• 残りの範囲（k番目からN-1番目まで）を反転します。

この手法なら、配列全体を数回走査するだけで済むため、時間計算量は O(N) に抑えられます。

コード例

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

void reverse(int nums[], int start,int end) {
    int temp=0;
    // 先頭要素と末尾要素を交換しながら配列を反転する
    while(start<=end){
        temp=nums[end];
        nums[end]=nums[start];
        nums[start]=temp;
        start++;
        end--;
    }
}

int main() {
    int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 };

    int N = sizeof(arr)/sizeof(arr[0]);

    int k = 4;
    // 配列全体を反転
    reverse(arr, 0, N-1);
    k = k%N;
    // 0番目からk-1番目までの範囲を反転

    reverse(arr, 0, k-1);
    // k番目から末尾までの範囲を反転
    reverse(arr, k, N-1);
    cout << "k要素回転後の配列 : ";
    for(int i = 0;i<N;i++)
        cout << arr[i] << " ";
    return 0;
}

出力

k要素回転後の配列 : 6 2 4 5 4 6 2 6 43 7 3

まとめ

この記事では、反転アルゴリズムを使って配列を右にk要素回転させる問題について解説しました。反転アルゴリズムの基本的な仕組み、その実装手順、そして実際のC++コードを紹介しました。同じロジックはC、Java、Pythonなど他のプログラミング言語でも簡単に応用できます。本記事が皆さんの学習のお役に立てば幸いです。