C++ では、O(1) 個の追加スペースを使用して配列を再配置し、正の項目と負の項目が交互になるようにします。

正と負の数値を含む整数型の配列 (たとえば、任意のサイズの arr[]) を取得します。ここでのタスクは、正の数値が負の数値で囲まれるように配列を再配置することです。もっとポジティブな気持ちがあれば、 負の数値は配列の最後にソートされます。

さまざまな入力と出力の状況を見てみましょう-

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

出力 - ソート前の配列: -1 -2 -3 1 2 3 正の項目と負の項目が交互になり、追加のスペースを必要としないように配列を再配置すると、 -1 1 -2 2 -3 3 となります。

説明: 正と負の要素を含むサイズ 6 の整数配列が与えられます。次に、余分なスペースを必要とせずに、すべての正の要素が負の要素の前に表示されるように配列を再配置します。 負の要素とすべての余分な要素で囲まれた -1 1 -2 2 -3 3 が最終配列の末尾に追加され、これが最終結果になります。

入力 - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};

出力 - ソート前の配列: -1 -2 -3 1 2 3 5 5 -5 3 1 1 追加のスペースを使用せずに配列を正負の項が交互に再配置する場合の時間計算量は O(1) です。 -1 1 -2 2 -3 3 -5 5 5 3 1 1

説明 - 正と負の要素を含むサイズ 12 の整数配列が与えられます。ここで、すべての正の要素が負の要素で囲まれるように配列を再配置し、すべての余分な要素を配列の最後に追加します。つまり、-1 1 -2 2 -3 3 -5 5 5 3 1 1 が最終結果。

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

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

• 再配置操作を実行する前に、FOR ループを使用して配列を出力します。

• 配列と配列サイズをパラメーターとして渡して、関数 Rearrangement(arr, size) を呼び出します。

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

  • 整数変数 'ptr' を宣言し、-1 に初期化します。

  • i が size 未満になるまで i から 0 までループします。ループ内で、ptr が 0 より大きいかどうかを確認し、次に arr[i] が 0 より大きく、arr[ptr] が 0 より小さいかどうか、または arr[i] が 0 より小さく、arr[ptr] が 0 より大きいかどうかを確認します。次に、関数 move_array(arr, size, ptr, i) を呼び出し、i - ptr が 2 より大きいかどうかを確認し、ptr を ptr 2 に設定します。それ以外の場合は、ptr を -1 に設定します。

  • ptr が -1 に等しいかどうかを確認し、arr[i] が 0 より大きく、かつ! (i & 0x01) または (arr[i] が 0 未満) であることを確認します。 (i & 0x01)、次に ptr を i に設定します。

• 関数 move_array(int arr[], int size, int ptr, int temp) 内で宣言されています

  • 「ch」という名前の文字型変数を arr[temp] に設定します。

  • i が ptr より大きくなるまで、i から temp までループします。ループ内で、arr[i] を arr[i - 1] に設定します。

  • arr[ptr]をchに設定します。

例

#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
   char ch = arr[temp];
   for(int i = temp; i > ptr; i--){
      arr[i] = arr[i - 1];
   }
   arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
   int ptr = -1;
   for(int i = 0; i < size; i++){
      if (ptr >= 0){
         if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
            move_array(arr, size, ptr, i);
            if(i - ptr >= 2){
               ptr = ptr + 2;
            }
            else{
               ptr = -1;
            }
         }
      }
      if(ptr == -1){
         if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
            ptr = i;
         }
      }
   }
}
int main(){
   //input an array
   int arr[] = {-1, -2, -3, 1, 2, 3};
   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 in alternating positive & negative items with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

出力

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

Array before Arrangement: -1 -2 -3 1 2 3
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3

以上がC++ では、O(1) 個の追加スペースを使用して配列を再配置し、正の項目と負の項目が交互になるようにします。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。