在C++中，使用O(1)额外空间重新排列数组，使正负项交替出现

我们得到一个包含正数和负数的整数类型数组，比方说，任意给定大小的 arr[] 。任务是重新排列一个数组，使得正数被负数包围。如果有更多的积极和 负数将被排列在数组的末尾。

让我们看看不同的输入输出情况 −

输入 − int arr[] = {-1, -2, -3, 1, 2, 3}

输出 − 排列前的数组：-1 -2 -3 1 2 3 重新排列一个数组，使正负项交替出现，并且不需要额外的空间是：-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。在循环内部，检查如果ptr大于0，然后检查如果arr[i]大于0且arr[ptr]小于0或arr[i]小于0且arr[ptr]大于0，则调用函数move_array(arr, size, ptr, i)，并检查如果i - ptr大于2，则将ptr设置为ptr + 2。否则，将ptr设置为-1。

  • 检查如果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

以上是在C++中，使用O(1)额外空间重新排列数组，使正负项交替出现的详细内容。更多信息请关注PHP中文网其他相关文章！