C++中O(n)时间和O(1)额外空间的正负数重排

给定一个包含正数和负数的整数类型数组，例如任意大小的arr[]。任务是重新排列数组，使所有正数和负数位于交替位置，如果存在额外的正数或负数元素，则将它们放在数组的末尾。

让我们看看各种输入输出场景：

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

输出 - O(n)时间和O(1)额外空间的正负数重排结果为：2 -1 6 -1 4 -3

解释 - 给定一个大小为6的整数数组，包含正数和负数元素。现在，我们将重新排列数组，使所有正数和负数元素位于交替位置，所有多余的元素将添加到数组的末尾，即2 -1 6 -1 4 -3是最终结果。

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

输出 - O(n)时间和O(1)额外空间的正负数重排结果为：2 -2 3 -5 5 -3 5 -1 1 3 1 1

解释 - 给定一个大小为12的整数数组，包含正数和负数元素。现在，我们将重新排列数组，使所有正数和负数元素位于交替位置，所有多余的元素将添加到数组的末尾，即2 -2 3 -5 5 -3 5 -1 1 3 1 1是最终结果。

下面程序中使用的方案如下：

  • 输入一个整数类型元素数组并计算数组的大小。

  • 使用FOR循环打印重新排列操作之前的数组。

  • 调用函数Rearrangement(arr, size)，并将数组和数组大小作为参数传递。

  • 在函数Rearrangement(arr, size)内部：

    • 声明临时整数类型变量，例如temp为-1，positive为temp + 1，negative为0。

    • 从i=0开始循环，直到i小于数组大小。在循环内，检查IF arr[i]小于0，则将temp加1，并调用C++ STL的内置方法swap(arr[temp], arr[i])，并将arr[temp]和arr[i]作为参数传递。

    • 启动WHILE循环，直到positive小于数组大小并且negative小于positive并且arr[negative]小于0。在循环内，调用swap，并将arr[negative]和arr[positive]作为参数传递。将positive加1，并将negative设置为negative + 2。

  • 打印结果。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

Open Compiler
#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]);
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   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

更新于：2021年11月2日

浏览量：309

开启您的职业生涯

完成课程获得认证

开始学习
广告