C ++でO（1）の余分なスペースを使用して、正と負の項目を交互に配列を再配置します

正の数と負の数の両方を含む整数型の配列、たとえば、任意のサイズのarr[]が与えられます。タスクは、負の数で囲まれる正の数になるように配列を再配置することです。より多くの正と負の数がある場合、それらは配列の最後に配置されます。

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

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

出力 −配置前の配列：-1 -2 -3 1 2 3 O（1）の余分なスペースがある正と負の項目を交互に並べた配列の再配置は次のとおりです：-1 1 -2 2 -3 3

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

入力 − 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）の余分なスペースがある正と負の項目を交互に並べた配列の再配置は次のとおりです。-11 -2 2 -3 3 -5 5 5 3 1 1

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

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

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

• FORループを使用して再配置アクションを実行する前に、配列を出力します。

• 配列と配列のサイズをパラメーターとして渡すことにより、関数Rearrangement（arr、size）を呼び出します。

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

  • 整数変数「ptr」を宣言し、-1で初期化します。

  • iがサイズより小さくなるまでiから0までループFORを開始します。ループ内で、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に設定します。それ以外の場合は、ptrを-1に設定します。

  • IF ptrを-1にチェックしてから、arr [i]が0より大きいAND！（i＆0x01）OR（arr [i]が0より小さい）AND（i＆0x01）をチェックしてから、ptrをiに設定します。

• 関数move_array（int arr []、int size、int ptr、int temp）内

  • 変数を文字型の「ch」として宣言し、arr[temp]で設定します。

  • iからtempまでのループFORを開始し、iがptrより大きくなるまで続けます。ループ内で、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