关于stable_partition的问题？

360U3148260177 2022-07-19 09:27

开发者_JAVA技巧

假设数组为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 开发者_如何学Python 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)

---