我们得到一个包含正数和负数的整数类型数组,比方说,任何给定大小的 arr[] 。任务是以这样的方式重新排列数组,即有一个正数将被负数包围。如果有更多的正负数,那么它们将排列在数组的末尾。
输入 - int arr[] = {-1, -2, -3, 1, 2, 3}
输出 - 排列前的数组:-1 -2 -3 1 2 3 用 O(1) 额外空间在交替的正负项中重新排列数组是:-1 1 -2 2 -3 3
说明 - 我们得到一个大小为 6 的整数数组,其中包含正元素和负元素。现在,我们将重新排列数组,使所有正元素都被负元素包围,所有额外的元素将添加到数组的末尾i.e-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 的整数数组,其中包含正元素和负元素。现在,我们将重新排列数组,使所有正元素都被负元素包围,所有额外的元素将添加到数组的末尾i.e-1 1 -2 2 -3 3 -5 5 5 3 1 1 将是最终结果。
输入整数类型元素的数组并计算数组的大小。
在使用 FOR 循环执行重新排列操作之前打印一个数组。
Rearrangement(arr, size)通过传递数组和数组大小作为参数来调用该函数。
函数内部 Rearrangement(arr, size)
声明一个整数变量 'ptr' 并用 -1 初始化它。
从 i 到 0 开始循环 FOR,直到 i 小于 size。在循环内部,检查 IF ptr 大于 0 然后检查 IF arr[i] 大于 0 AND arr[ptr] 小于 0 或 arr[i] 小于 0 AND arr[ptr] 大于 0 然后调用函数move_array(arr, size, ptr, i)和检查如果 i - ptr 大于 2,然后将 ptr 设置为 ptr + 2。否则,将 ptr 设置为 -1。
检查 IF ptr 为 -1 然后检查 arr[i] 大于 0 AND !(i & 0x01) OR (arr[i] 小于 0) AND (i & 0x01) 然后将 ptr 设置为 i。
在函数 move_array(int arr[], int size, int ptr, int temp) 内部
将变量声明为字符类型的 '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