题目：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。
大概就是要求stable_partition的实现，然而stl中stable_partition实现利用了额外的空间，不符合题目要求呢。
正常会有两种实现方法：
（一）用一个游标，从前往后遍历，第一次遇到负数则继续，遇到正数则记录并接着走，再遇到负数则与刚记录的正数互换，并将记录后移一位，这样遍历完成的时候移位也完成了。
（二）用两个游标，一个位于数组头，往后遍历，一个位于数组尾，往前遍历。前面的遇到负数后面的遇到正数组则继续；前面的遇到正数后面的遇到负数则互换，直到后面游标小于前面游标算完成。
但是都不满足稳定性的要求，毕竟快排是不稳定的排序。
那这题应该怎么做呢。再花o(n)时间，把后半部分不稳定的地方给找到再rotate？？感觉好蛋疼。
巴扎黑2017-04-17 15:00:20
/**
1. 元の順序を維持したい場合は、順番に移動するか、隣接するものを入れ替えることしかできません。
2.i 左から右にトラバースして、最初の偶数を見つけます。
3.j 最初の奇数が見つかるまで、i+1 から逆方向の検索を開始します。
4. [i,...,j-1] のすべての要素を 1 ビット戻し、最後に見つかった奇数を i の位置に入れ、次に i++ を入れます。
5. 終了条件: j 後方走査に失敗しました。
*/
高洛峰2017-04-17 15:00:20
必要な時間の計算量は 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 番目のコピー -2 は位置 1 [-1, -2, 1, 2, 3, 4]
後で他に負の数が見つからなければ、終了です。
黄舟2017-04-17 15:00:20
各数字の移動が予想される位置は固定されており、予測可能です。シミュレーション観察を通じて、対応する数値が毎回期待される位置に移動される限り、現在位置の値が期待される位置に移動し続けることがわかりました。この場合、シフト全体は実際には M 個の部分文字列の循環シフトになります。重要なのは、各点の予想される変位位置をどのように知るかです。
最初のパスでは、正の数と負の数の合計数 P と N を取得するので、分割点がどこにあるかを知ることができます。
2 番目のパスは、負の領域の正と負の数 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 から始まります。
2巡目シフトは6->11->13->6
3巡目シフトは7->12->14->15-7
終了。各要素は 1 回だけ移動されるため、時間計算量は O(N) です。
使用される空間は 5、空間複雑度は O(1) です
----以下の答えの時間計算量は O(N^2) です--更新された答えは上です--
負の数が o、正の数が x であると仮定します。
前から後ろにトラバースし、xx..xoo..o の部分文字列が見つかるたびに、oo..oxx..x へ循環左シフトを実行します。
次回新しい値を計算するとき、変換する前の x xx..xoo..o 部分文字列パターンから開始します。
各文字は最大 2 回操作されるため、複雑さは O(N) です。
残りは、xx..xoo..o を変更することで、O(L) の複雑さ内で oo.oxx..x の変更を完了することです。パターン文字列が x1x2x3x4o1o2o3 であると仮定し、範囲内で 2 回反転します。最初に 2 つの部分文字列を個別に反転すると、x4x3x2x1o3o2o1 が得られ、2 回目に文字列全体を反転すると、o1o2o3x1x2x3x4 が得られます。仕上げる。合計2*L回。
まとめると、時間計算量は O(N) で、各要素は最大 4 回移動します。空間計算量は O(1) です。
