# Reorder array

• Given a descending array A, reorder it to: Ln→L0→Ln-1→L1→Ln-2→L2→…
e.g. A = [7, 6, 5, 4, 3, 2, 1] → A = [1, 7, 2, 6, 3, 5, 4]

NOTICE: do this with only O(1) memory space and in O(n) time complexity.

• public void change(int[] arr){
int start = 0;
int end = arr.length - 1;
int seg = arr.length / 3;
//System.out.println("seg : " + seg);
reverse(arr, start, end);
start += 2;
reverse(arr, start, end);

for(int i = 0; i < seg; i++){
start += 3;
reverse(arr, start, end);
}
int point = 1;
for(int i = 0; i < seg; i++){
swap(arr, point + i * 3, point + i * 3 + 1);
}
}

• @shall_strom

private void reverse(int[] arr, int start, int end){
while(start < end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

• public void change(int[] arr) {
int len = arr.length - 1;
for (int i = 0; i <= len; i++) {
reverse(i, len);
}
}

• Inspired by this Rotate Problemt , it has a solution Using Cyclic Replacements. Just change it a little, I add a function to find the right index of the nextone. It can also solve other similar array problem with constant place. Just change the nextone function.

Using Cyclic Replacements

int nextone(int cur,int n)
{
if(cur<n/2)
return 1+cur*2;
else return (n-cur-1)*2;
}
void reorder(vector<int>& nums){
int n=nums.size();
int start;
int count=0;
for(start=n-1;count<n;start--)
{
int cur=start;
int pre=nums[start];
do{
int next=nextone(cur,n);
int tmp=nums[next];
nums[next]=pre;
pre=tmp;
cur=next;
count++;
}while(start!=cur);
}
return;
}

• @2015E8007361069 i also find it has some regulars,but it's too hard to find it for me.you are good.

• @2015E8007361069 seems your code doesn't work when n=10

problem happens on start--;

start may encounter a position which was swapped

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.