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

1. 问题描述

给定一个由正数和负数组成的数组，要求重新排列数组中的元素，使得所有负数元素排在正数元素之前。并且要保持原有元素的相对顺序不变。要求以O(n)的时间复杂度和O(1)的额外空间完成这个操作。

2. 思路分析

2.1 双指针法

最简单的思路是使用双指针法。我们用一个指针从左往右扫描数组，如果遇到一个负数，则将其和左侧第一个正数交换位置。因为我们要保持原有元素的相对顺序，所以左侧第一个正数的位置就是当前指针的位置。

下面来看一下这个算法的示例：

void rearrange(vector<int>& nums) {
  int i = 0;
  int j = 0;
  while (i < nums.size() && j < nums.size()) {
    while (i < nums.size() && nums[i] < 0) {
      ++i;
    }
    j = max(i + 1, j);
    while (j < nums.size() && nums[j] <= 0) {
      ++j;
    }
    if (j < nums.size()) {
      swap(nums[i++], nums[j++]);
    }
  }
}

这个算法很简单，时间复杂度为O(n)，但是空间复杂度不为O(1)，因为我们需要使用额外的指针。

2.2 不使用额外指针

我们可以不使用额外的指针，而是将指针i和指针j的位置储存在数组里面。同时，我们用一个变量k来记录当前正数的起始位置。当我们找到一个负数时，我们就将前面所有的正数依次往后移动一位，然后将当前负数放入数组中k指向的位置。下面看一下代码：

void rearrange(vector<int>& nums) {
  int k = 0;
  for (int i = 0; i < nums.size(); ++i) {
    if (nums[i] < 0) {
      int j = i;
      while (j > k) {
        swap(nums[j], nums[j - 1]);
        --j;
      }
      ++k;
    }
  }
}

这个算法的时间复杂度仍然为O(n)，但是空间复杂度为O(1)。

3. 总结

以上两个算法都能在O(n)的时间复杂度内完成这个问题。不使用额外指针的算法以O(1)的空间复杂度完美解决了这个问题，但是代码稍微比较复杂，而双指针算法的代码比较简单，但是空间复杂度不为O(1)。

因此，在选择算法时，可以根据实际情况进行选择。