arr が arr] になるように配列を再配置し、O(1) 個の余分なスペースのみを使用します。C++ で実装されています。

正の整数型の配列、たとえば、任意のサイズの arr[] を取得します。配列内の要素の値は 0 より大きく、サイズより小さい必要があります。配列。任務は再配置することです 指定された O(1) 空間内で arr[i] を arr[arr[i]] に変換するだけの配列で、最終結果を出力します。

この状況におけるさまざまな入出力シナリオを見てみましょう -

Input- int arr[] = {0 3 2 1 5 4 }

出力- ソート前の配列: 0 3 2 1 5 4 arr[i] が arr[arr[i]] になるように配列を再配置し、O(1) 個の余分なスペースを追加します: 0 1 2 3 4 5

説明- Define を与えます。サイズ 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.

input− int arr[] = {1, 0}

output − ソート前の配列: 1 0 arr[i] が arr[arr[i]] になるように配列を再配置します。ここで、O(1) 個の余分なスペースは次のとおりです: 0 1

説明 - サイズ 2 の整数を取得します。配列内のすべての要素が 2 未満の値を持つ配列。ここで、arr[arr[0]] が 1、arr[arr[1]] が 0 になるように配列を再配置します。したがって、再配置後の最終的な配列は 0 1 になります。

Input- int arr[] = {1, 0, 2, 3}

Output-ソート前の配列: 1 0 2 3 arr[i] が arr[arr[i]] になるように配列を再配置し、O(1) 個の余分なスペースを追加します: 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 になります。

次のプログラムで使用するメソッドは次のとおりです。

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

• 配列を出力する前に関数を呼び出します 再配置 (arr, size)

• 関数内部再配置 (arr, size)

  • i からループ FOR を開始しますi が size 未満になるまで 0 になります。ループ内で、temp を arr[arr[i]] % size および arr[i] = temp * size に設定します。

  • i が size 未満になるまで、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

以上がarr が arr] になるように配列を再配置し、O(1) 個の余分なスペースのみを使用します。C++ で実装されています。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。