在 C++ 中以 O(n) 时间和 O(1) 额外空间重新排列正负数

  • Z时代
  • 2024-01-10
  • 分类：综合

我们得到一个包含正数和负数的整数类型数组，比方说，任何给定大小的 arr[] 。任务是以这样一种方式重新排列数组，即所有正数和负数应处于交替位置，如果有额外的正或负元素，则它们将被放置在数组的末尾。

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

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

输出 - 在O(n)时间和 O(1) 额外空间中重新排列正负数是：2 - 1 6 -1 4 -3

说明 - 我们得到一个大小为 6 的整数数组，其中包含正元素和负元素。现在，我们将重新排列数组，使所有正元素和负元素位于交替位置，并且所有额外元素将添加到数组的末尾i.e2 -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 的整数数组，其中包含正元素和负元素。现在，我们将重新排列数组，使所有正元素和负元素位于交替位置，所有额外元素将添加到数组的末尾i.e2 -2 3 -5 5 -3 5 - 1 1 3 1 1 将是最终结果

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

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

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

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

  • 函数内部 Rearrangement(arr, size)

    • 将临时整数类型变量 ietemp 声明为 -1，将正数声明为 temp + 1，将负数声明为 0。

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

    • 开始循环 WHILE 小于数组大小的正数 AND 负数小于正数 AND arr[negative] 小于 0。在循环内，通过传递 arr[negative] 和 arr[positive] 作为参数来调用 swap。将正数增加 1，并将负数设置为负数 + 2。

  • 打印结果。

示例

#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]);
   //调用函数重新排列数组
   Rearrangement(arr, size);
   //重新排列值后打印数组
   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

以上是 在 C++ 中以 O(n) 时间和 O(1) 额外空间重新排列正负数 的全部内容， 来源链接： utcz.com/z/359463.html

回到顶部