在 C++ 中以 O(n) 时间和 O(1) 额外空间重新排列正负数
我们得到一个包含正数和负数的整数类型数组，比方说，任何给定大小的arr[]。任务是以这样一种方式重新排列数组，即所有正数和负数应处于交替位置，如果有额外的正或负元素，则它们将被放置在数组的末尾。
让我们看看这个的各种输入输出场景-
输入 -intarr[]={4,2,-1,-1,6,-3}
输出 -在O(n)时间和O(1)额外空间中重新排列正负数是：2-16-14-3
说明 -我们得到一个大小为6的整数数组，其中包含正元素和负元素。现在，我们将重新排列数组，使所有正元素和负元素位于交替位置，并且所有额外元素将添加到数组的末尾i.e2-16-14-3将是最终结果
输入 -intarr[]={-1,-2,-3,1,2,3,5,5,-5,3,1,1}
输出 -O(n)时间和O(1)额外空间中正负数的重新排列是：2-23-55-35-11311
说明-我们得到一个大小为12的整数数组，其中包含正元素和负元素。现在，我们将重新排列数组，使所有正元素和负元素位于交替位置，所有额外元素将添加到数组的末尾i.e2-23-55-35-11311将是最终结果
下面程序中使用的方法如下
输入整数类型元素的数组并计算数组的大小。
在使用FOR循环执行重新排列操作之前打印一个数组。
Rearrangement(arr,size)通过传递数组和数组大小作为参数来调用该函数。
函数内部Rearrangement(arr,size)
将临时整数类型变量ietemp声明为-1，将正数声明为temp+1，将负数声明为0。
从i到0开始循环FOR，直到i小于数组的大小。在循环内部，检查IFarr[i]小于0然后将temp增加1并调用C++STL的内置方法即swap(arr[temp],arr[i])并传递arr[temp]和arr[i]作为参数。
开始循环WHILE小于数组大小的正数AND负数小于正数ANDarr[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]);
//调用函数重新排列数组
Rearrangement(arr, size);
//重新排列值后打印数组
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