C++程序 在O(n)时间内并使用O(1)额外空间重新排列正负数

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),因为我们没有使用任何额外的空间。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例