C++で配列の要素をその場（インプレース）で反転するプログラム

問題概要

n個の異なる要素からなる配列が与えられたとき、配列内の要素を反転して表示するプログラムを作成します。ここでのポイントは、単に逆順に表示するだけではなく、配列自体の要素をその場（インプレース）で入れ替えることです。

例として、入力が n = 9、arr = [2,5,6,4,7,8,3,6,4] の場合、出力は [4,6,3,8,7,4,6,5,2] となります。

アルゴリズム

この問題は、以下の手順で解くことができます。

• i を 0 から n/2 未満まで 1 ずつ増やしながら、以下を繰り返します。
  • temp に arr[i] の値を退避する
  • arr[i] に arr[n - i - 1] を代入する
  • arr[n - i - 1] に temp を代入する
• i を 0 から n 未満まで 1 ずつ増やしながら、arr[i] を表示します。

この手法では、配列の先頭と末尾から順にペアとなる要素を交換していくため、別の配列を用意する必要がなく、空間計算量 O(1) で反転を実現できます。時間計算量は O(n) です。

C++による実装例

#include <iostream>
using namespace std;
int main(){
    int n = 9;
    int arr[n] = {2,5,6,4,7,8,3,6,4};
    int temp;
    for(int i = 0; i<n/2; i++){
        temp = arr[i];
        arr[i] = arr[n-i-1];
        arr[n-i-1] = temp;
    }
    for(int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
}

入力

9, {2,5,6,4,7,8,3,6,4}

出力

4 6 3 8 7 4 6 5 2