本文共 858 字，大约阅读时间需要 2 分钟。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
循环左移4位：
| 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 |
题目：设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面尽可能高效的算法。将R中的序列循环左移P（0<P<n）个位置，即将R中的数据由（x0，x1，…，xn-1）变换为（xp，Xp+1，…，Xn-1，x0，x1，…，Xp-1）。要求： （1）给出算法的基本设计思想。 （2）根据设计思想，用程序设计语言描述算法，关键之处给出注释。
（3）说明你设计算法的时间复杂度和空间复杂度。
分析：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0~p-1位逆置，p~n-1位逆置：
| 3 | 2 | 1 | 0 | 9 | 8 | 7 | 6 | 5 | 4 |
整体逆置：
| 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 |
答：
（1）算法思想：a代表前p个元素，b代表数组中余下的n-p个元素。可以将这个问题看成将数组ab转换成ba，现将a逆置得到a逆，再将b逆置得到b逆，最后整体逆置就得到了ba。（线性代数知识，有数组逆置的实现）
（2）代码（这次不是伪代码）：
void Reverse(int R[], from, to){ int i, temp; for(i=0; i<(to-from+1)/2; i++){ temp = R[from+i]; R[from+i] = R[to-i]; R[to-i] = temp; }}void Converse(int R[], int n, int p){ Reverse(R, 0, p-1); Reverse(R, p, n-1); Reverse(R, 0, n-1);} （3）时间复杂度：Reverse(R, 0, p-1);执行了3*(p/2)步，Reverse(R, p, n-1);执行了3*(n-p)/2 ，Reverse(R, 0, n-1);执行了3*(n/2)，共3n步。该算法的时间复杂度O(n)
只用到了一个额外的temp变量，所需辅助空间为常量。该算法空间复杂度为O(1)。
转载地址：http://peeii.baihongyu.com/