如题，如有数组abcd1234,让数组向右边移动两位，变成了34abcd12,现在要求在特定长度的数组array中，要求移动n位，并在0(n)的时间复杂度下完成。
如果是首先我们假定数组的长度是L，如果移动的位数大于L的话，其实等同于移动了n%L位，我们如果按照循环的方式来移动数组，可得如下的代码
n=%L;
//移动n位
for(int i=0;i
temp = array[L-1];
for(int j=L-2;j>=0;j--){
array[j+1] = array[j];
}
array[j+1] = temp;
}
这样做，其实时间复杂度是0(n*L),这样其实并不符合题目要求达到0（n）的要求。
其实对于每一个移动的数组，我们可以看到，其实移动的过程可以分解为以下的方式。
如1234abcd如果要求向右移动四位，那么移动的过程可以这样看。
先是前四位翻转，然后是后四位，最后是整个数组在翻转。
1234abcd->4321abcd->4321dcba->abcd1234
代码如下
int reverse(int n,int m,int *A){
for(;n>m;n++,m--){
temp = A[n];
A[n] = A[m];
A[m] = temp;
}
}
int main(){
int n;//移动的位数
reserve(0,n-1,A);
reserve(n,L-n-1,A);
reserve(0,n-1,A);
}
这样子只涉及数字的移动，时间复杂度是0（n）
阅读(2541) | 评论(0) | 转发(0) |
