题目：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。
大概就是要求stable_partition的实现，然而stl中stable_partition实现利用了额外的空间，不符合题目要求呢。
正常会有两种实现方法：
（一）用一个游标，从前往后遍历，第一次遇到负数则继续，遇到正数则记录并接着走，再遇到负数则与刚记录的正数互换，并将记录后移一位，这样遍历完成的时候移位也完成了。
（二）用两个游标，一个位于数组头，往后遍历，一个位于数组尾，往前遍历。前面的遇到负数后面的遇到正数组则继续；前面的遇到正数后面的遇到负数则互换，直到后面游标小于前面游标算完成。
但是都不满足稳定性的要求，毕竟快排是不稳定的排序。
那这题应该怎么做呢。再花o(n)时间，把后半部分不稳定的地方给找到再rotate？？感觉好蛋疼。
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
/**
으아악1. 원래 순서를 유지하고 싶다면 순차적으로 이동하거나 인접한 순서만 바꿀 수 있습니다.
2.i 왼쪽에서 오른쪽으로 탐색하여 첫 번째 짝수를 찾습니다.
3.j 첫 번째 홀수를 찾을 때까지 i 1부터 역방향 검색을 시작합니다.
4. [i,...,j-1]의 모든 요소를 한 비트 뒤로 이동하고 마지막으로 찾은 홀수를 i 위치에 넣은 다음 i 를 넣습니다.
5. 종료조건 : j 역방향 탐색 실패.
*/
교환하지 말고 복사만 하세요. 필요한 시간 복잡도는 o(n)이기 때문입니다.
배열이
.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]
나중에 다른 음수가 발견되지 않으면 종료입니다.
각 숫자가 이동할 것으로 예상되는 위치는 고정되어 있으며 예측 가능합니다. 시뮬레이션 관찰을 통해 해당 숫자가 매번 예상 위치로 이동하는 한 현재 위치의 값이 예상 위치로 계속 이동한다는 것을 발견했습니다. 그러면 전체 이동은 실제로 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부터 시작됩니다.
2차 교대는 6->11->13->6
3차 교대는 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 하위 문자열 패턴에서 시작합니다.
각 문자는 최대 2번 연산되므로 복잡도는 O(N)입니다.
나머지는 xx..xoo..o를 변경하여 O(L) 복잡도 내에서 oo.oxx..x의 변경을 완료하는 것입니다. 패턴 문자열이 x1x2x3x4o1o2o3이라고 가정하고 범위 내에서 두 번 반전하면 두 하위 문자열이 개별적으로 처음으로 반전되면 x4x3x2x1o3o2o1이 되고 두 번째로 전체 문자열을 반전하면 o1o2o3x1x2x3x4가 됩니다. 마치다. 총 2*L회.
정리하자면, 시간 복잡도는 O(N)이고, 각 요소는 최대 4번 이동합니다. 공간 복잡도는 O(1)