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

在日常生活和数学计算中，常常需要将一个数组中的正数和负数分别进行处理，例如将所有正数复制到另一个数组或者将所有负数取相反数。而有时候，需要重新排列这个数组，使得其左边为所有负数，右边为所有正数。那么如何用C++编写程序，在O(n)时间内并使用O(1)额外空间重新排列正负数呢？

通过观察题目，我们可以发现只要把数组中的正数和负数重新排列，其他元素的顺序并不改变。而解决这个问题的核心思想就是：使用双指针，分别从左右两端向中间扫描数组，将不符合要求的元素交换位置。

例如将数组int arr[] = {2, -4, 3, -1, -4, 0, 5, -6};重新排列后可以得到{-4, -1, -4, -6, 2, 3, 5, 0}。

以下是用C++实现该算法的代码：

#include <iostream>
using namespace std;

void reArrange(int arr[], int n)
{
    int left = 0;
    int right = n-1;

    while(left <= right){
        if(arr[left] < 0 && arr[right] < 0){
            // 左侧是负数，右侧也是负数，则交换
            swap(arr[left], arr[right]);
            left++;
        }else if(arr[left] > 0 && arr[right] < 0){
            // 左侧是正数，右侧是负数，则交换
            swap(arr[left], arr[right]);
            left++;
            right--;
        }else if(arr[left] > 0 && arr[right] > 0){
            // 左侧是正数，右侧也是正数，则不需要交换
            right--;
        }else{
            // 左侧是负数，右侧是正数，则不需要交换
            left++;
            right--;
        }
    }
}

int main()
{
    int n = 8;
    int arr[] = {2, -4, 3, -1, -4, 0, 5, -6};

    reArrange(arr, n);

    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";

    return 0;
}

代码说明：

函数 reArrange(int arr[], int n) 用于重新排列数组arr。其中，数组长度为n。
双指针left和right分别从左右两端向中间扫描数组。
当left指向的元素为负数且right指向的元素为负数时，左指针右移，继续扫描。
当left指向的元素为正数且right指向的元素为负数时，将两个元素交换，left指针右移，right指针左移。
当left指向的元素为正数且right指向的元素为正数时，右指针左移，继续扫描。
当left指向的元素为负数且right指向的元素为正数时，left指针右移，right指针左移，继续扫描。

解决方案

此算法分为三个步骤:

初始化指向数组左端和右端的两个指针（left和right）。
循环遍历数组，将left和right指针都往中间移动，直到left大于等于right，遍历结束。
在遍历的过程中，通过观察left指针和right指针当前指向的元素，让指针执行合适的操作。根据题目要求，我们需要将数组中的负数排在左边，正数排在右边。因此，我们有以下四种情况：