c++ - 关于stable_partition的问题

Question

题目：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。

大概就是要求stable_partition的实现，然而stl中stable_partition实现利用了额外的空间，不符合题目要求呢。

正常会有两种实现方法：

（一）用一个游标，从前往后遍历，第一次遇到负数则继续，遇到正数则记录并接着走，再遇到负数则与刚记录的正数互换，并将记录后移一位，这样遍历完成的时候移位也完成了。

（二）用两个游标，一个位于数组头，往后遍历，一个位于数组尾，往前遍历。前面的遇到负数后面的遇到正数组则继续；前面的遇到正数后面的遇到负数则互换，直到后面游标小于前面游标算完成。

但是都不满足稳定性的要求，毕竟快排是不稳定的排序。
那这题应该怎么做呢。再花o(n)时间，把后半部分不稳定的地方给找到再rotate？？感觉好蛋疼。

Answer 1

/**

• 1. If you want to maintain the original order, you can only move them sequentially or swap adjacent ones.

• 2.i Traverse from left to right and find the first even number.

• 3.j Start searching backward from i+1 until you find the first odd number.

• 4. Move all the elements of [i,...,j-1] back one bit, and finally put the found odd number into the i position, and then i++.

• 5. Termination condition: j backward traversal search failed.
  */

void reOrderArray(vector<int> &array) {
    if(array.empty())
        return;
    int index1=0;
    int index2=0;
    for(int i=0;i<array.size();i++){
        if((array[i]&1)==1){
            int temp=array[i];
            for(int j=i;j>index1;j--){
                swap(array[j],array[j-1]);
            }
            array[index1]=temp;
            index1++;
        } 
    }
}

Answer 2

Don’t do exchange, just copy. Because the required time complexity is o(n).

Assume the array is a,
1. First find the first integer, remember the position is i, then find the first negative number encountered later, the position is j, save a[j] to a temporary variable , copy the number in the range a[i, j-1] to a[i+1, j], and assign the temporary variable to a[i],
2. Position i stores the found negative number
3 .Continue starting from j+1, find the next negative number, the position is k, save a[k] to a temporary variable, copy a[i+1, k-1] to a[i+2, k], assign the temporary variable Give a[i+1]
4. At this time, i+1 stores the negative number just found
5. Continue the previous process

Example:
Initial [1, -1, 2, -2, 3, 4]
First copy, -1 is placed at position 0 [-1, 1, 2, -2, 3 , 4]
Copy for the second time, place -2 at position 1 [-1, -2, 1, 2, 3, 4]
If no other negative numbers are found later, it is over.

Answer 3

The position where each number is expected to be moved is fixed and predictable. Through simulation observation, we found that as long as the corresponding number is moved to its expected position each time, then continue to move the value of the current position to the expected position. Then the entire shift is actually a circular shift of M substrings. The key is how to know the expected displacement position of each point.
In the first pass, we get the total numbers P and N of positive and negative numbers, so we can know where the dividing point is.
The second pass traverses the positive and negative numbers PL and NL in the negative area.
k1 represents the number of negative numbers on the right that have been moved to the left.
k2 represents the number of positive numbers on the right that have been moved.
k3 represents the number of negative numbers on the left that have been moved.
k4 represents the number of positive numbers on the left that have been moved.
i points to the starting point of the negative area, and j points to the starting point of the positive area.
If the current position is on the left (its real-time starting point on the left), if it is a positive number, move to the k4 position on the right. (The positions all start at 0). If it is a negative number, move to the k3 position on the left.
If the current position is to the right. If the current number is positive, move to the PL+k2 position on the right; if it is a negative number, move to the NL+k1 position on the left.
Any time when the moving target position is equal to the initial starting position, the current circular shift ends.
The starting point of the next cycle is the first positive position on the left, which is the position of k1+k3.

Example:
Use o to represent negative numbers and x to represent positive numbers.
The original string is
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
x o o x x o x x o o o x x o x o

The dividing point is 0,7
The shift pattern of the first round is 0->8->3->9->4->10->5->2- >1->0
After the first round, k1=3, k3=3, then the starting point of the next round starts from 6.
The second round shift is 6->11->13->6
The third round shift is 7->12->14->15-7
End. Each element is moved only once, so the time complexity is O(N).
The space used is 5, and the space complexity is O(1)

----The time complexity of the answer below is O(N^2)--the updated answer is above--
Assume that the negative number is o and the positive number is x.
Traverse from front to back, each time you find the substring of xx..xoo..o, perform a circular left shift to oo..oxx..x;
The next time you calculate a new one, start from the previous x xx..xoo..o substring pattern to convert.
Each character is operated on at most twice, so the complexity is O(N).
The rest is to complete the change of oo.oxx..x within O(L) complexity by changing xx..xoo..o. Assume that the pattern string is x1x2x3x4o1o2o3 and invert it twice within the range. The first time is to invert the two substrings separately to get x4x3x2x1o3o2o1, and the second time to invert the whole string is to get o1o2o3x1x2x3x4. Finish. A total of 2*L times.
To sum up, the time complexity is O(N), and each element is moved up to 4 times. The space complexity is O(1)