给定有N个元素数组，将之循环移K位，不能使用库函数，不能使用辅助数组，要求时间复杂度为O(N)
解法1：
思路：
（1） 整个数组倒序
（2）0 - K位倒序
（3）K - (N-1)位倒序
代码：
void printArray(int a[],int n){
for(int i=0;i<n;i++){
printf("%d\t",a[i]);
}
printf("\n");
}
void reverse(int a[], int begin, int end){
int n = (end-begin+1)/2;
for(int i=0;i<n;i++){
int t = a[begin+i];
a[begin+i] = a[end-i-1];
a[end-i-1] = t;
}
}
void shift(int a[], int n, int k){
k = (n+k%n)%n;
reverse(a,0,n);
reverse(a,0,k);
reverse(a,k,n);
}
void main(){
int a[] = {1,2,3,4,5,6,7,8};
int n = sizeof(a)/sizeof(int);
printArray(a,n);
//shift(a,n,-1);
shift(a,n,4);
printArray(a,8);
}
解法2：
void Output(int *pBuffer, int nCount)
{
if(!pBuffer || !nCount) return;
for (size_t i = 0; i < nCount; i++)
{
printf(" %d ", pBuffer[i]);
}
printf("\n");
}
void ShiftN(int *pBuffer, int nCount, int nShiftN)
{
if(!pBuffer || !nCount || !nShiftN) return;
nShiftN %= nCount;
int nIndex = 0;
int nStart = nIndex;
int nTemp = pBuffer[nIndex];
for (size_t i = 0; i < nCount; i++)
{
nIndex = (nIndex + nShiftN) % nCount;
pBuffer[nIndex] ^= nTemp ^=
pBuffer[nIndex] ^= nTemp ;
if(nIndex == nStart)
{
nStart ++;
nIndex = nStart;
nTemp = pBuffer[nIndex];
}
}
}
int main(int argc, char* argv[])
{
int buffer[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int nCount = sizeof(buffer) / sizeof(int);
Output(buffer, nCount);
ShiftN(buffer, nCount, 8);
Output(buffer, nCount);
return 0;
}
posted on 2009-06-07 12:00
iConnect 阅读(394)
评论(0) 编辑 收藏 所属分类:
数学&算法&数据结构