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)。
因此，在选择算法时，可以根据实际情况进行选择。