在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 -1 4 -3 將是最終結果

輸入

輸入

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 到 0 循環，直到 i 小於陣列的大小。在循環內部，檢查IF arr[i] 小於0，然後將temp 加1 並呼叫C STL 的內建方法，即swap(arr[temp], arr[i]) 並傳遞arr[temp] 和arr[i ]作為參數。

  • 開始循環，WHILE 正數小於陣列大小 AND 負數小於正數 AND arr[負數] 小於 0。在迴圈內，呼叫透過傳遞 arr[負數] 和 arr[正數] 作為參數進行交換。將正數加 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中文網其他相關文章！