我們得到一個包含正數和負數的整數型別數組，比方說，任意給定大小的 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中文網其他相關文章！
