題目：假設一整型數組存在若干正數和負數，現在通過某種算法使得該數組的所有負數在正數的左邊，且保證負數和正數間元素相對位置不變。時空復雜度要求分別為：o(n)和o(1)。

大概就是要求stable_partition的實現，然<愛尬聊_尬聊百科>而stl中stable_partition實現利用了額外的空間，不符合題目要求呢。

正常會有兩種實現方法：

（一）用一個游標，從前往后遍歷，第一次遇到負數則繼續，遇到正數則記錄并接著走，再遇到負數則與剛記錄的正數互換，并將記錄后移一位，這樣遍歷完成的時候移位也完成了。

（二）用兩個游標，一個位于數組頭，往后遍歷，一個位于數組尾，往前遍歷。前面的遇到負數后面的遇到正數組則繼續；前面的遇到正數后面的遇到負數則互換，直到后面游標小于前面游標算完成。

但是都不滿足穩定性的要求，畢竟快排是不穩定的排序。
那這題應該怎么做呢。再花o(n)時間，把后半部分不穩定的地方給找到再rotate？？感覺好蛋疼。

---

360U3148260177 2022-07-19 09:27

假設數組為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.繼續前面的過程

---

這大學該不該上66 2022-07-19 09:29

不要做交換，做拷貝就可以了. 因為要求時間復雜度為o(n).

---

M25****202 2022-07-19 09:44

例子:初始 [1, -1, 2, -2, 3, 4] 第一次拷貝，-1放在位置0 [-1, 1, 2, -2, 3, 4]第二次拷貝，-2放在位置1 [-1, -2, 1, 2, 3, 4]后面沒找到其它負數，就結束了.

---

愛電影愛分享 2022-07-19 09:45

假設負數是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)

---