c++ - 关于stable_partition的问题

Question

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

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

正常会有两种实现方法：

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

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

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

Answer 1

/**

• 1.要想保证原有次序，则只能顺次移动或相邻交换。

• 2.i从左向右遍历，找到第一个偶数。

• 3.j从i+1开始向后找，直到找到第一个奇数。

• 4.将[i,...,j-1]的元素整体后移一位，最后将找到的奇数放入i位置，然后i++。

• 5.終止條件：j向後遍歷查找失敗。
  */

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

不要做交换，做拷贝就可以了. 因为要求时间复杂度为o(n).

假设数组为a,
1.先找到第一个整数，记好位置为i，然后找到后面遇到的第一个负数,位置为j, 保存a[j]到临时变量里，将a[i, j-1]区间的数拷贝给a[i+1, j], 临时变量赋值给a[i]，
2.位置i存放的是找到的负数
3.继续从j+1开始，找到下一个负数，位置为k, a[k]保存到临时变量, 拷贝a[i+1, k-1] 到 a[i+2, k], 临时变量赋值给a[i+1]
4.此时i+1存放的是刚找到的负数
5.继续前面的过程

例子:
初始 [1, -1, 2, -2, 3, 4]
第一次拷贝，-1放在位置0 [-1, 1, 2, -2, 3, 4]
第二次拷贝，-2放在位置1 [-1, -2, 1, 2, 3, 4]
后面没找到其它负数，就结束了.

Answer 3

每个数字期望被移到的位置是固定的，可预期的。通过模拟观察发现，只要每次将对应的数字移到它期望的地方，之后继续移动当前位置的值到期望位置。则真个移位最终其实是M个子串的循环移位。那关键就是如何知道每一个点的期望移位位置。
第一遍遍历得到正数、负数的各自的总个数P和N，因此可以知道分界点在哪里。
第二遍遍历负数区域里的正数和负数个数PL和NL。
k1表示右侧的负数往左侧移动过的个数。
k2表示右侧的正数移动过的个数。
k3表示左侧的负数移动过的个数。
k4表示左侧的正数移动过的个数。
i指向负数区域的起点，j指向正数区域的起点。
如果当前位置在左侧（其实时在左侧起点），如果是正数，则移动到右侧的k4位置。（位置都是0开始）。如果是负数，则移动到左侧的k3位置。
如果当前位置再右侧。如果当前是正数，移到右侧的第PL+k2位置；如果是负数，则移动到左侧的NL+k1位置。
任何时候当移动的目标位置等于最初的起点位置后，当前循环移位结束。
下一步循环开始的起点在左侧的第一个正数位置，也就是k1+k3的位置。

举例：
用o表示负数，用x表示正数。
原始串为
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

分界点在0,7
第一轮的移位模式为 0->8->3->9->4->10->5->2->1->0
第一轮之后k1=3, k3=3, 则下一轮的起点从6开始。
第二轮的移位为6->11->13->6
第三轮的移位为7->12->14->15-7
结束。每个元素只移动过一次，所以时间复杂度为O(N)。
使用的空间是5个，空间复杂度为O(1)

----下述答案的时间复杂度是O(N^2)--更新后的答案在上面--
假设负数是o，正数是x。
从前往后遍历，每次找到xx..xoo..o的子串，进行循环左移变为oo..oxx..x;
下一次从上一次的x开始计算新的xx..xoo..o子串模式来转换。
每个字符最多被操作两次，因此复杂度是O(N)。
剩下的就是如果将xx..xoo..o在O(L)的复杂度内完成oo.oxx..x的变化。假设模式串为x1x2x3x4o1o2o3, 范围内两次倒置，第一次将两个子串分别反转，得到x4x3x2x1o3o2o1，第二次整体倒置得到o1o2o3x1x2x3x4。完成。一共是2*L次。
综上，时间复杂度O(N)，每个元素最多移动了4次.空间复杂度O(1)