C ++を使用して、arr[i]がO（1）の余分なスペースでarr[arr[i]]になるように配列を再配置します。

正の整数型の配列、たとえば、配列内の要素の値が0より大きく、配列のサイズよりも小さい任意のサイズのarr[]が与えられます。タスクは、指定されたO（1）スペース内でのみarr[i]がarr[arr [i]]になるように配列を再配置し、最終結果を出力することです。

このためのさまざまな入出力シナリオを見てみましょう-

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

出力 −配置前の配列：0 3 2 1 5 4 arr[i]がO（1）の余分なスペースで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です。したがって、再配置後の最終的な配列は012です。 3 4 5.

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

出力 −配置前の配列：1 0 arr[i]がO（1）の余分なスペースでarr [arr [i]]になるように配列を再配置すると、次のようになります。0 1

説明 −サイズ2の整数配列と、2未満の配列値のすべての要素が与えられます。次に、配列を再配置します。つまり、arr [arr [0]は1、arr [arr[1]]は0です。 、再配置後の最終的な配列は01です。

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

出力 −配置前の配列：1 0 2 3 arr[i]がO（1）の余分なスペースで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 123です。

以下のプログラムで使用されているアプローチは次のとおりです

• 整数型要素の配列を入力し、配列のサイズを計算します

• 配列の前に配列を印刷し、関数Rearrangement（arr、size）を呼び出します

• 関数Rearrangement（arr、size）の内部

  • iがサイズより小さくなるまでiから0までループFORを開始します。ループ内で、tempをarr [arr [i]]％sizeおよびarr [i] + =temp*sizeとして設定します。

  • iがサイズより小さくなるまでiから0までループFORを開始します。ループ内で、arr [i] =arr [i] / size

    を設定します

• 結果を印刷します。

例

#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(){
   //input an array
   int arr[] = {0, 3, 2, 1, 5, 4};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   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