資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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是最終結果。
輸入 - 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 3 1 1是最終結果。
下面程式中使用的方案如下：
輸入一個整數型別元素陣列並計算陣列的大小。
使用FOR迴圈列印重新排列操作之前的陣列。
呼叫函式Rearrangement(arr, size)，並將陣列和陣列大小作為引數傳遞。
在函式Rearrangement(arr, size)內部：
宣告臨時整數型別變數，例如temp為-1，positive為temp + 1，negative為0。
從i=0開始迴圈，直到i小於陣列大小。在迴圈內，檢查IF arr[i]小於0，則將temp加1，並呼叫C++ STL的內建方法swap(arr[temp], arr[i])，並將arr[temp]和arr[i]作為引數傳遞。
啟動WHILE迴圈，直到positive小於陣列大小並且negative小於positive並且arr[negative]小於0。在迴圈內，呼叫swap，並將arr[negative]和arr[positive]作為引數傳遞。將positive加1，並將negative設定為negative + 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
瀏覽量：309
