C++でarr[i]がjの場合、arr[j]がiとなるように配列を再配置する方法

ここでは、正の整数型の配列 arr[](任意のサイズ)が与えられます。配列内の各要素は、0以上かつ配列のサイズ未満の値でなければなりません。この課題の目的は、「arr[i] の値が j であれば、arr[j] を i にする」という規則に従って配列を再配置し、その最終結果を出力することです。

入出力シナリオの例

入力 − int arr[] = {3, 4, 1, 2, 0}

出力 −
再配置前の配列: 3 4 1 2 0
「arr[i]がjならばarr[j]をiにする」ように再配置した配列: 4 2 3 0 1

説明 − サイズ5の整数配列が与えられ、すべての要素は5未満の値です。各要素の対応関係を見てみましょう。arr[0]が3なのでarr[3]には0を、arr[1]が4なのでarr[4]には1を、arr[2]が1なのでarr[1]には2を、arr[3]が2なのでarr[2]には3を、arr[4]が0なのでarr[0]には4を格納します。したがって、最終的な配列は「4 2 3 0 1」となります。

入力 − int arr[] = {2, 0, 1, 3}

出力 −
再配置前の配列: 2 0 1 3
「arr[i]がjならばarr[j]をiにする」ように再配置した配列: 1 2 0 3

説明 − サイズ4の整数配列が与えられ、すべての要素は4未満の値です。arr[0]が2なのでarr[2]には0を、arr[1]が0なのでarr[0]には1を、arr[2]が1なのでarr[1]には2を、arr[3]が3なのでarr[3]には3を格納します。したがって、最終的な配列は「1 2 0 3」となります。

プログラムで使用しているアプローチ

• 整数型の要素からなる配列を入力として受け取り、配列のサイズを計算します。

• 再配置前の配列を出力し、関数 Rearrangement(arr, size) を呼び出します。

• 関数 Rearrangement(arr, size) の内部では、次の処理を行います。

  • 配列 arr[] と同じサイズの整数型補助配列 ptr[] を作成します。

  • i を 0 から size 未満までループさせ、ループ内で ptr[arr[i]] に i を代入します。

  • 再度 i を 0 から size 未満までループさせ、ループ内で arr[i] に ptr[i] を代入します。

• 再配置後の配列の値を出力します。

この方法では、補助配列 ptr[] を利用することで、元の配列の情報を失うことなく各要素を正しい位置へ移動できます。時間計算量は O(n)、追加で必要なメモリも O(n) であり、非常に効率的な手法です。

コード例

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
    int ptr[size];
    for(int i = 0; i < size; i++){
        ptr[arr[i]] = i;
    }
    for(int i = 0; i < size; i++){
        arr[i] = ptr[i];
    }
}
int main(){
    // 配列の入力
    int arr[] = {3, 4, 1, 2, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    // 元の配列を出力
    cout<<"Array before Arrangement: ";
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    // 配列を再配置する関数を呼び出し
    Rearrangement(arr, size);
    // 再配置後の配列を出力
    cout<<"\nRearrangement of an array such that 'arr[j]' becomes 'i' if 'arr[i]' is 'j' is: ";
    for(int i = 0; i < size; i++){
        cout<< arr[i] << " ";
    }
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

Array before Arrangement: 3 4 1 2 0
Rearrangement of an array such that 'arr[j]' becomes 'i' if 'arr[i]' is 'j' is: 4 2 3 0 1