首页 > 文章列表 > 在C++中,使用固定额外空间重新排列正数和负数

在C++中,使用固定额外空间重新排列正数和负数

排列 正负数 固定额外空间
337 2023-09-18

我们有一个包含正数和负数的整数类型数组,假设是任意给定大小的arr[]。任务是重新排列数组,使得数组的所有元素都使用C++ STL的内置排序函数以及使用递归进行排序 技术编码和打印结果。

让我们看看这个的各种输入输出场景 −

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

输出 − 重新排列正负数,使用恒定的额外空间:-3 -1 -1 0 6 2 4。

解释 − 我们给出一个大小为7的整数数组,包含正数和负数元素。现在,我们将重新排列数组,使得数组中的所有元素在恒定的额外空间内排序,最终结果将是-3 -1 -1 0 2 4 6。

输入 − int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}

输出 − 重新排列正负数,使用恒定的额外空间:-9 -10 2 3 10 5 8 4

解释 − 我们给出一个大小为8的整数数组,包含正数和负数元素。现在,我们将重新排列数组,使得数组中的所有元素在恒定的额外空间内排序,最终结果将是-9 -10 2 3 10 5 8 4。

下面程序中使用的方法如下

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

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

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

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

    • 将一个整数类型变量i设置为0,将j设置为size -1。

    • 开始while(true)。在while内部,开始另一个循环,当arr[i]小于0且i小于size时,递增i。

    • 开始WHILE arr[j]大于0且j大于0时,递减j。

    • 检查IF i小于j,然后设置temp为arr[i],arr[i]为arr[j],arr[j]为temp。

    • 否则,跳出循环。

  • 打印结果。

示例

#include<iostream>
using namespace std;
void Rearrangement(int arr[], int size){
   int i = 0;
   int j = size - 1;
   while(true){
      while(arr[i] < 0 && i < size){
         i++;
      }
      while(arr[j] > 0 && j >= 0){
         j--;
      }
      if (i < j){
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
      }
      else{
         break;
      }
   }
}
int main(){
   int arr[] = {4, 2, -1, -1, 6, -3, 0};
   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 with constant extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

输出

如果我们运行上面的代码,将会生成以下输出

Rearrangement of positive and negative numbers with constant extra space is: -3 -1 -1 0 6 2 4