Question

数据结构算法（并说明时间复杂度和空间复杂度）

设n(n>1)个整数存放在一维数组R中。设计一个在时间和空间两方面尽可能高效的算法。将R中保存的整数序列循环左移P(0<P<n)个位置，即将R中的数据由(X0，X1，…，Xn-1)变换为(Xp，Xp+1，…，Xn-1，X0，X1，…，Xp-1)。要求设计算法并说明算法的时间复杂度和空间复杂度。

Answer 1

算法主要用了一个额外的先入后出的线性表（即栈），假定数组为Num[n],流程如下：
1.先申请一个能存放n个整数的栈。
2.把原有数组的后n-p个元素，从后面Num[n-1]到Num[p]开始依次压入栈。
3.把数组的前p个元素，从Num[p-1]开始，把Num[n-1]=Num[p-1],依次类推，直到
Num[n-p]=Num[0].
4.把栈中的数弹出，依次放入数组Num[0]、Num[1]····中，直到放完。
5，这样所得的结果就是所需要的结果。
时间复杂度O(n),空间复杂度也是O(n).