C++でO(1)の追加メモリを使い、arr[i]をarr[arr[i]]になるように配列を並べ替える方法

正の整数型の配列 arr[] が与えられます。配列のサイズは任意ですが、すべての要素は 0 以上かつ配列のサイズ未満である必要があります。この課題の目的は、O(1) の追加メモリ領域しか使わずに、arr[i] が arr[arr[i]] となるように配列を再配置し、その最終結果を出力することです。

入出力シナリオの例

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

出力 −
並べ替え前の配列: 0 3 2 1 5 4
O(1) の追加メモリで arr[i] を arr[arr[i]] に並べ替えた結果: 0 1 2 3 4 5

説明 − サイズ 6 の整数配列が与えられ、すべての要素は 6 未満です。ここで、arr[arr[0]] = 0、arr[arr[1]] = 1、arr[arr[2]] = 2、arr[arr[3]] = 3、arr[arr[4]] = 4、arr[arr[5]] = 5 となるように再配置します。したがって、再配置後の最終的な配列は 0 1 2 3 4 5 となります。

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

出力 −
並べ替え前の配列: 1 0
O(1) の追加メモリで arr[i] を arr[arr[i]] に並べ替えた結果: 0 1

説明 − サイズ 2 の整数配列が与えられ、すべての要素は 2 未満です。ここで、arr[arr[0]] = 1、arr[arr[1]] = 0 となるように再配置します。したがって、再配置後の最終的な配列は 0 1 となります。

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

出力 −
並べ替え前の配列: 1 0 2 3
O(1) の追加メモリで arr[i] を arr[arr[i]] に並べ替えた結果: 0 1 2 3

説明 − サイズ 4 の整数配列が与えられ、すべての要素は 4 未満です。ここで、arr[arr[0]] = 0、arr[arr[1]] = 1、arr[arr[2]] = 2、arr[arr[3]] = 3 となるように再配置します。したがって、再配置後の最終的な配列は 0 1 2 3 となります。

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

• 整数型の要素からなる配列を入力として受け取り、配列のサイズを計算します。
• 並べ替え前の配列を出力し、関数 Rearrangement(arr, size) を呼び出します。
• 関数 Rearrangement(arr, size) の内部では次の処理を行います。
  • i を 0 から size 未満までループさせます。ループ内では temp = arr[arr[i]] % size とし、arr[i] += temp * size を実行します。これにより、1 つの要素に「元の値」と「新しい値」の両方を一時的に格納できます。
  • 続けて i を 0 から size 未満までループさせ、arr[i] = arr[i] / size を実行します。これにより、新しい値だけが取り出されます。
• 結果を出力します。

この手法のポイントは、配列のサイズ n を基数として利用することです。arr[i] % n で元の値を、arr[i] / n で新しく格納した値をそれぞれ復元できるため、補助配列を一切使わずに O(n) 時間・O(1) 空間で並べ替えが完了します。

コード例

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
    for(int i=0; i < size; i++){
        int temp = arr[arr[i]] % size;
        arr[i] += temp * size;
    }
    for(int i = 0; i < size; i++){
        arr[i] = arr[i] / size;
    }
}
int main(){
    // 配列の入力
    int arr[] = {0, 3, 2, 1, 5, 4};
    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 so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
    for(int i = 0; i < size; i++){
        cout<< arr[i] << " ";
    }
    return 0;
}

出力

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

Array before Arrangement: 0 3 2 1 5 4
Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5