在 C++ 中用 O(1) 额外空间在交替的正负项中重新排列数组
我们得到一个包含正数和负数的整数类型数组，比方说，任何给定大小的arr[]。任务是以这样的方式重新排列数组，即有一个正数将被负数包围。如果有更多的正负数，那么它们将排列在数组的末尾。
让我们看看这个的各种输入输出场景-
输入 -intarr[]={-1,-2,-3,1,2,3}
输出 -排列前的数组：-1-2-3123用O(1)额外空间在交替的正负项中重新排列数组是：-11-22-33
说明 -我们得到一个大小为6的整数数组，其中包含正元素和负元素。现在，我们将重新排列数组，使所有正元素都被负元素包围，所有额外的元素将添加到数组的末尾i.e-11-22-33将是最终的结果。
输入 -intarr[]={-1,-2,-3,1,2,3,5,5,-5,3,1,1};
输出 -排列前的数组：-1-2-312355-5311用O(1)额外空间在交替的正负项中重新排列数组是：-11-22-33-555311
说明-我们得到一个大小为12的整数数组，其中包含正元素和负元素。现在，我们将重新排列数组，使所有正元素都被负元素包围，所有额外的元素将添加到数组的末尾i.e-11-22-33-555311将是最终结果。
下面程序中使用的方法如下
输入整数类型元素的数组并计算数组的大小。
在使用FOR循环执行重新排列操作之前打印一个数组。
Rearrangement(arr,size)通过传递数组和数组大小作为参数来调用该函数。
函数内部Rearrangement(arr,size)
声明一个整数变量'ptr'并用-1初始化它。
从i到0开始循环FOR，直到i小于size。在循环内部，检查IFptr大于0然后检查IFarr[i]大于0ANDarr[ptr]小于0或arr[i]小于0ANDarr[ptr]大于0然后调用函数move_array(arr,size,ptr,i)和检查如果i-ptr大于2，然后将ptr设置为ptr+2。否则，将ptr设置为-1。
检查IFptr为-1然后检查arr[i]大于0AND!(i&0x01)OR(arr[i]小于0)AND(i&0x01)然后将ptr设置为i。
在函数move_array(intarr[],intsize,intptr,inttemp)内部
将变量声明为字符类型的'ch'并使用arr[temp]设置它。
从i到temp开始循环FOR，直到i大于ptr。在循环内，将arr[i]设置为arr[i-1]。
将arr[ptr]设置为ch。
示例
#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
char ch = arr[temp];
for(int i = temp; i > ptr; i--){
arr[i] = arr[i - 1];
}
arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
int ptr = -1;
for(int i = 0; i < size; i++){
if (ptr >= 0){
if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
move_array(arr, size, ptr, i);
if(i - ptr >= 2){
ptr = ptr + 2;
}
else{
ptr = -1;
}
}
}
if(ptr == -1){
if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
ptr = i;
}
}
}
}
int main(){
//输入一个数组
int arr[] = {-1, -2, -3, 1, 2, 3};
int size = sizeof(arr) / sizeof(arr[0]);
//打印原始数组
cout<<"排列前的数组： ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//调用函数重新排列数组
Rearrangement(arr, size);
//重新排列值后打印数组
cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
排列前的数组： -1 -2 -3 1 2 3 Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3