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);
}
}
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