数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 在 O(1) 空间复杂度内重排数组，使其正负数交替排列
给定一个包含正数和负数的整数类型数组，例如任意大小的 arr[]。任务是重排数组，使其正数被负数包围。如果正数和负数数量不一致，则多余的数将排列在数组的末尾。
让我们看看这个任务的不同输入输出场景：
输入 - int arr[] = {-1, -2, -3, 1, 2, 3}
输出 - 数组重排前：-1 -2 -3 1 2 3 使用 O(1) 额外空间在数组中交替排列正负数的结果是：-1 1 -2 2 -3 3
解释 - 我们得到一个大小为 6 的整数数组，包含正数和负数元素。现在，我们将重排数组，使所有正数被负数包围，所有多余的元素都添加到数组的末尾，即 -1 1 -2 2 -3 3 将是最终结果。
输入 - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};
输出 - 数组重排前：-1 -2 -3 1 2 3 5 5 -5 3 1 1 使用 O(1) 额外空间在数组中交替排列正负数的结果是：-1 1 -2 2 -3 3 -5 5 5 3 1 1
解释 - 我们得到一个大小为 12 的整数数组，包含正数和负数元素。现在，我们将重排数组，使所有正数被负数包围，所有多余的元素都添加到数组的末尾，即 -1 1 -2 2 -3 3 -5 5 5 3 1 1 将是最终结果。
下面程序中使用的方案如下
输入一个整数类型元素的数组并计算数组的大小。
使用 FOR 循环打印执行重排操作之前的数组。
调用函数 Rearrangement(arr, size)，并将数组和数组大小作为参数传递。
在函数 Rearrangement(arr, size) 内部
声明一个整数变量 'ptr' 并将其初始化为 -1。
从 i 为 0 开始循环到 i 小于 size。在循环内部，检查 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。否则，将 ptr 设置为 -1。
检查 IF ptr 为 -1，然后检查 arr[i] 大于 0 并且 !(i & 0x01) 或 (arr[i] 小于 0) 并且 (i & 0x01)，则将 ptr 设置为 i。
在函数 move_array(int arr[], int size, int ptr, int temp) 内部
声明一个字符类型的变量 'ch' 并将其设置为 arr[temp]。
从 i 为 temp 开始循环到 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(){
//input an array
int arr[] = {-1, -2, -3, 1, 2, 3};
int size = sizeof(arr) / sizeof(arr[0]);
//print the original Array
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//calling the function to rearrange the array
Rearrangement(arr, size);
//print the array after rearranging the values
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;
}输出
如果我们运行以上代码，它将生成以下输出
Array before Arrangement: -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
609 次浏览
