题目要求是这样的：
/*
设将n (n > 1) 个整数存放到一维数组 R中。设计一个在时间和空间两方面尽可能高效的算法。
将 R 中的序列循环左移 p（0 < p < n）个位置，即将 R 中的数据由 (a0, a1, ……an-1)
变换为(ap, ap-1, …an-1, a0, a1, …, ap-1)。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用C或C++或JaVa语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
*/
下面是我的一个低效实现：
#include <iostream>
bool circleLeftMove( int nArr[], int nSize, int nMove )
{
//判断边界条件
if( nSize <= 1 )
{
return false;
}
if( nMove <= 0 || nMove >= nSize )
{
return false;
}
//将需要移动的前nMove个数移动到一个缓存中
int *pTemp = new int[nMove];
for( int i=0; i<nMove; ++i )
{
pTemp[i] = nArr[i];
}
//移动nMove开始的剩余数到0～(nSize - nMove)位置上
int nStart = nMove;
for( int j=0; j<(nSize-nMove); ++j )
{
nArr[j] = nArr[nStart++];
}
//将缓存中的数据放到原始数组后面
nStart = nSize-nMove;
for( int i=0; i<nMove; ++i )
{
nArr[nStart++] = pTemp[i];
}
//释放缓存
delete []pTemp;
return true;
}
void print( int arr[], int nSize )
{
for(int i=0; i<nSize; ++i )
{
std::cout << “Num” << i << “==>” << arr[i] << std::endl;
}
}
int main(int argc, char *argv[])
{
int nArr[]={0,1,2,3,4,5,6};
std::cout << “Before Circle Move:” << std::endl;
print( nArr, sizeof(nArr)/sizeof(nArr[0]) );
int nMove;
std::cout << “Please Input The Move Count:”;
std::cin >> nMove;
std::cout << std::endl;
circleLeftMove( nArr, sizeof(nArr)/sizeof(nArr[0]), nMove );
std::cout << “After Circle Move “ << nMove << std::endl;
print( nArr, sizeof(nArr)/sizeof(nArr[0]) );
return 0;
}
只是稍微测试了下，查看参考答案后发现这个算法叫做海豚算法，下面是其给出的参考实现：
大致思路为：
首先把序列{ a0, a1, …, ap, …, an-1 }逆转为{an-1, an-2, …, ap, …,a0 }，
再分别逆转{ an-1, an-2, …, ap }和{ ap-1, ap-2, …,a0 }，
最后得到{ ap, ap+1, …, an-1, a0, …, ap-1}。
void reverse ( int A[ ], int left, int right )
{
int n = right-left+1;
if ( n <= 1 ) return;
if ( n <= 1 ) return;
for ( int i = 0; i < n/2; i++ )
{
int temp = A[i];
A[i] = A[n-i-1];
A[n-i-1] = temp;
}
}
void sift_Left ( int a[ ], int n, int p )
{
reverse ( a, 0, n-1 );
reverse ( a, 0, n-p-1 );
reverse ( a, n-p, n-1 );
}
我实现的那个空间复杂度比较高O(p)，参考答案的为O(1)，时间上面都是O(n)。
通过比较其他实现，发现自己在算法方面确实需要提高，我完全是按照那种常规思路来实现，没有进行任何优化，这在效率有要求的时候显然就不行了，这里还悟出一点道理，高效算法一般都不是大多数人想到的那种常规方法，即根据要求一步步满足，而应该根据算法输出结果来分析其中的规律进而找到突破点。