Rearrange Array

• Time : $O(n)$
• Space : $O(1)$

void Solution::arrange(vector<int> &A) {
    for(int i = 0; i < A.size(); i++) {
        if(A[i] < 0) continue;
        if(A[A[i]] == A[i]) continue;
        int origin = A[A[i]], now = A[i];
        while(now >= 0 and A[origin] >= 0) {
            swap(A[origin], A[now]);
            int pos = origin;
            origin = A[now];
            if(A[now] == 0) A[now] = INT_MIN;
            else if(A[now] > 0) A[now] = -A[now];
            now = pos;
        }
        if(A[i] == 0) A[i] = INT_MIN;
        else if(A[i] > 0) A[i] = -A[i];
    }
    
    for(int i = 0; i < A.size(); i++) {
        if(A[i] == INT_MIN) A[i] = 0;
        else if(A[i] < 0) A[i] = -A[i];
    }
}