C++でarr[i] = iとなるように配列を再配置する方法

任意のサイズの正の整数型配列 arr[] が与えられます。配列内の各要素は、0 より大きく配列のサイズ未満の値を持つものとします。ここでの課題は、配列を再配置することです。具体的には、インデックス i に対応する値 i が配列内に存在する場合は arr[i] = i とし、存在しない場合には arr[i] に -1 を設定した上で、最終的な結果を出力します。

入出力シナリオの例

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

出力 − arr[i] = i となるように再配置した配列: 0 1 2 3 4 5 -1 -1

説明 − サイズ 8 の整数配列が与えられ、すべての要素は 8 未満です。そこで、配列を以下のように再配置します。

arr[0] = 0（配列内に存在）
arr[1] = 1（配列内に存在）
arr[2] = 2（配列内に存在）
arr[3] = 3（配列内に存在）
arr[4] = 4（配列内に存在）
arr[5] = 5（配列内に存在）
arr[6] = -1（配列内に存在しない）
arr[7] = -1（配列内に存在しない）

入力 − int arr[] = {1, 2, 6, 9, 10}

出力 − arr[i] = i となるように再配置した配列: -1 1 2 -1 -1

説明 − サイズ 5 の整数配列が与えられ、すべての要素は 5 未満です。そこで、配列を以下のように再配置します。

arr[0] = -1（配列内に存在しない）
arr[1] = 1（配列内に存在）
arr[2] = 2（配列内に存在）
arr[3] = -1（配列内に存在しない）
arr[4] = -1（配列内に存在しない）

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

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

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

• 関数 Rearranging(arr, size) の内部処理は以下の通りです。

  • 整数型変数 ptr を宣言します。

  • i を 0 から size 未満まで繰り返す FOR ループを開始し、その中でさらに j を 0 から size 未満まで繰り返す FOR ループを実行します。

  • 内側のループの中で arr[j] == i であるかどうかを判定し、真であれば ptr = arr[j]、arr[j] = arr[i]、arr[i] = ptr と値を入れ替えた後、break でループを抜けます。

  • 続いて、i が size 未満である間ループを実行し、arr[i] != i である場合には arr[i] に -1 を設定します。

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

コード例

#include <iostream>
using namespace std;
void Rearranging(int arr[], int size){
   int ptr;
   for(int i = 0; i < size; i++){
      for(int j = 0; j < size; j++){
         if(arr[j] == i){
            ptr = arr[j];
            arr[j] = arr[i];
            arr[i] = ptr;
            break;
         }
      }
   }
   for(int i = 0; i < size; i++){
      if(arr[i] != i){
         arr[i] = -1;
      }
   }
}
int main(){
   int arr[] = {0, 8, 1, 5, 4, 3, 2, 9 };
   int size = sizeof(arr) / sizeof(arr[0]);
   //arr[i] = i となるように配列を再配置する関数を呼び出す
   Rearranging(arr, size);
   //配列の出力
   cout<<"Rearrangement of an array such that arr[i] = i is: ";
   for(int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
}

出力

上記のコードを実行すると、以下の出力が生成されます。

Rearrangement of an array such that arr[i] = i is: 0 1 2 3 4 5 -1 -1

補足：計算量について

このアプローチでは二重のネストされたループを使用しているため、時間計算量は O(n²) となります。一方、余分な補助領域を使用していないため、空間計算量は O(1) です。なお、ハッシュセットなどの補助データ構造を利用して要素の存在確認を O(1) で行うことで、全体の計算量を O(n) まで改善できる点にも触れておきます。