C++程序 在O(n)时间内并使用O(1)额外空间重新排列正负数
一个数组包含随机顺序的正数和负数。重新排列数组元素,以便正数和负数交替放置。正数和负数的数量不必相等。如果有更多的正数,它们出现在数组的末尾。如果有更多的负数,它们也出现在数组末尾。
例如,如果输入数组为[-1,2,-3,4,5,6,-7,8,9],则输出应为[9,-7,8,-3,5,-1,2,4,6]。
注意: 分区过程会改变元素的相对顺序。即,此方法不维护元素出现的顺序。查看此处以保持元素出现顺序的解决方案。
解决方案是首先使用QuickSort的分区过程将正数和负数分开。在分区过程中,将0视为枢轴元素的值,以便将所有负数放在正数之前。一旦分离了负数和正数,我们从第一个负数和第一个正数开始,并交替交换每个负数和下一个正数。
//一个C++程序将正数放置于偶数索引(0,2,4,..),
//并将负数放置在奇数索引(1、3、5、..)。
#include
using namespace std;
class GFG
{
public:
void rearrange(int [],int);
void swap(int *,int *);
void printArray(int [],int);
};
//重排给定数组元素的主要函数。将正
//元素放在偶数索引(0,2,..)并将负数
//数字在奇数索引(1,3,..)。
void GFG :: rearrange(int arr[], int n)
{
//以下几行类似于QuickSort的分区过程。
//思路是将0视为枢轴,将其周围的数组分开。
int i = -1;
for (int j = 0; j < n; j++)
{
if (arr[j] < 0)
{
i++;
swap(&arr;[i], &arr;[j]);
}
}
//现在所有的正数都在结尾,而负数在
//开始式。初始化正数和负数的起始点的索引
//需要交换
int pos = i + 1, neg = 0;
//将负数索引增加2而将正数索引增加1,
//即交换每个负数索引的相邻的下一个正数
while (pos < n && neg < pos && arr[neg] < 0)
{
swap(&arr;[neg], &arr;[pos]);
pos++;
neg += 2;
}
}
//交换两个元素的实用程序函数
void GFG :: swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//打印数组的实用程序函数
void GFG :: printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
//驱动代码
int main()
{
int arr[] = {-1, 2, -3, 4,
5, 6, -7, 8, 9};
int n =sizeof(arr) / sizeof(arr[0]);
GFG test;
test.rearrange(arr, n);
test.printArray(arr, n);
return 0;
}
//此代码是由vt_Yogesh Shukla 1贡献的
输出
4 -3 5 -1 6 -7 2 8 9
时间复杂度: O(n),其中n是给定数组中的元素数。因为我们使用循环遍历N次,所以它将花费O(N)时间。
辅助空间: O(1),因为我们没有使用任何额外的空间。