数据结构
2010-42
设将 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）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
答案
答案：
（1）算法基本设计思想
将数组视为前p个元素组成的子数组a和后n-p个元素组成的子数组b。通过三次逆置操作实现循环左移：先逆置a，再逆置b，最后逆置整个数组。即先将数组ab转换为a⁻¹b，再转换为a⁻¹b⁻¹，最终得到ba。
（2）算法描述（C语言）
void Reverse(int R[], int from, int 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); // 逆置前p个元素
Reverse(R, p, n - 1); // 逆置后n-p个元素
Reverse(R, 0, n - 1); // 逆置整个数组
}（3）时间复杂度和空间复杂度
时间复杂度：O(n)，其中三次逆置操作总代价为O(p + (n-p) + n) = O(n)。
空间复杂度：O(1)，仅使用常数个临时变量。