C++ では、正の数と負の数を O(n) の時間計算量と O(1) の追加スペースで並べ替えます。

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

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

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

出力− 正の数値と負の数値を O(n) 回と O(1) 回で並べ替えます。余分なスペースは次のとおりです: 2 - 1 6 -1 4 -3

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

Input

入力

Strong>− int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}

出力 strong>- 正と負の数値を 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 3 1 1 になります。結果

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

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

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

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

• 内部関数 Rearrangement(arr, size)

  • 一時整数変数を宣言します。つまり、temp は -1、正の数は temp 1 です。 , 負の数は0です。

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

  • 正の数が配列サイズより小さく、かつ負の数が正の数より小さく、かつ arr[負の数] が 0 より小さい条件でループを開始します。ループ内では、arr[negative] と arr[positive] を引数として渡すことによって呼び出しが交換されます。正の数に 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

以上がC++ では、正の数と負の数を O(n) の時間計算量と O(1) の追加スペースで並べ替えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。