C ++でO（n）時間とO（1）余分なスペースで正と負の数を並べ替えます

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

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

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

出力 − O（n）時間とO（1）余分なスペースでの正と負の数の再配置は次のとおりです。2-1 6 -1 4 -3

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

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

出力 − O（n）時間とO（1）余分なスペースでの正と負の数の再配置は次のとおりです。2-2 3 -5 5 -3 5 -1 1 3 1 1

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

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

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

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

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

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

  • 一時的な整数型変数を宣言します。つまり、tempを-1に、正をtemp + 1に、負を0に宣言します。

  • iから0まで、iが配列のサイズより小さくなるまでループFORを開始します。ループ内で、IF arr [i]が0未満であることを確認してから、温度を1ずつインクリメントし、C ++ STLの組み込みメソッド、つまりswap（arr [temp]、arr [i]）を呼び出し、arr[temp]とarr[i]を渡します。 ]パラメータとして。

  • ループを開始します。正の値が配列のサイズより小さく、負の値が正の値より小さく、arr [negative]が0未満です。ループ内で、パラメーターとしてarr[negative]とarr[positive]を渡してswapを呼び出します。正の値を1増やし、負の値を負の値+2に設定します。

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   int temp = -1;
   for(int i = 0; i < size; i++){
      if (arr[i] < 0){
         temp++;
         swap(arr[temp], arr[i]);
      }
   }
   int positive = temp + 1;
   int negative = 0;
   while(positive < size && negative < positive && arr[negative] < 0){
      swap(arr[negative], arr[positive]);
      positive++;
      negative = negative + 2;
   }
}
int main(){
   int arr[] = {4, 2, -1, -1, 6, -3};
   int size = sizeof(arr)/sizeof(arr[0]);
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

出力

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

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3