题目来源： 计算机考研408真题2010年42题
题目描述：
- 描述: 42.(13分）设将n(n>1)个整数存放到一维数组R中。 试设计一个在时间和空间两方面都尽可
能高效的算法。将R中保存的序列循环(移p(O<p<n)个位置，即将R中的数据由 ( X 0 , X 1 , … , X n − 1 ) (X_0,X_1,…,X_{n-1}) (X0,X1,…,Xn−1)变换为 ( X p , X p + 1 , . . . , X n − 1 , X 0 , X 1 , . . . , X p − 1 ) (X_p,X_{p+1},...,X_{n-1},X_0,X_1,...,X_{p-1}) (Xp,Xp+1,...,Xn−1,X0,X1,...,Xp−1)。
要求：
1）给出算法的基本设计思想。
2)根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
示例1:
输入：{0,1,2,3,4},3
输出：{3,4,0,1,2}
思路
- 将数组R看作是前后两个数组AB的组成，其中A代表数组R的前p个元素，B代表数组R的剩余n-p个元素，根据题意可知，只需要将AB变为BA即可，使用
逆序的方法即可
具体实现:
- 假设数组R为01234，其中p=3
- step1：用
Reverse()将数组A也就是R中(0,p-1)的元素进行逆序,得到数组A：210
- step2：用
Reverse()将数组B也就是R中(p,n-p)的元素进行逆序,得到数组B：43
- step3：用
Reverse()将数组R中(0,n-1)的元素进行逆序,得到34012
具体实现:
public class day408_09 {static void Reverse(int arr[], int start, int end){int i ,temp;for(i = 0;i < (end-start+1)/2;i++){temp = arr[start+i];arr[start+i] = arr[end-i];arr[end - i] = temp;}}static void Converse(int arr[], int n, int p){Reverse(arr,0,p-1);Reverse(arr,p,n-1);Reverse(arr,0,n-1);}public static void main(String[] args) {int[] arr = {0,1,2,3,4};for(int i = 0;i < arr.length;i++){System.out.print(arr[i]);}Converse(arr,5,3);for(int i = 0;i < arr.length;i++){System.out.print(arr[i]);}}
}
- 将数组[start, end]范围内的元素逆序还有更明了的写法
-
static void Reverse(int arr[], int start, int end){int i ,temp;while (start < end) {temp = arr[start];arr[start++] = arr[end];arr[end--] = temp;}}
