学步园

输入n与数组t，正数表示数组往左移动n位，负数表示数组往右移动n位。

要求时间为n阶，空间为1

来自于结构之法的作者，较好的算法是：

将一个字符串分成两部分，X和Y两个部分，在字符串上定义反转的操作X^T，即把X的
所有字符反转（如，X="abc"，那么X^T="cba"），那么我们可以得到下面的结论：
(X^TY^T)^T=YX。显然我们这就可以转化为字符串的反转的问题了。
其实这种运算在矩阵的翻转求逆等运算中多得是，和牛人的差距就是怎么都联系不起来。。。。汗

琢磨了半天自己想了个类似于辗转相减法的实现，和原pdf中的算法2差不多，java代码如下：

/**
	 * 实现左移或者或者右移数组n位
	 * 时间复杂度为O(n),空间为O(1)
	 * @param t   要移动的数组
	 * @param n   n为数组要移动的位数，n>0 左移,n<0右移
	 * @return
	 */
	public <T> T[] rotate(T[] t,int n){
		if(n==0)
			return t;
		boolean right = false;
		if(n<0){//需要往右移动
			n = Math.abs(n);
			right = true;
		}
			
		if(n>t.length){//超过长度取模，因为移一个数组长度等于没移
			n = n%t.length;
		}
		if(right){
			n = t.length-n;//往右移n位等于往左移动t.length-n位
		}
		//分为2个子序列，移动到尾部的子序列A和要移动到头部的子序列B
		int start = 0;//序列A的头部和尾部索引
		int end = n-1;
		int aLength = end -start+1;
		int bLength = t.length- n;//序列B的长度 
		
		T temp;//用来交换值的临时变量
		
		while(true){
			if(end-start+1==bLength){//类似于2整数辗转相减法，所以相等条件可以达到
				for(int i=start;i<=end;i++){
					temp=t[i];t[i]=t[i+aLength];t[i+aLength]=temp;//java值传递，
										//不可以调用函数互换值，形参互换对实参无意义
				}
				break;
			}else if(aLength<bLength){//A序列长度小于B序列
				for(int i=start;i<=end;i++){//那就将B序列中起点开始的等于A序列长度
					temp=t[i];t[i]=t[i+aLength];t[i+aLength]=temp;//的序列和A互换
				}							//将B序列部分值放到应该放到位置
				start = end+1;				//同时B序列的长度减少了
				end = start+aLength-1;
				bLength = bLength - aLength;
			}else{//A序列的长度大于B序列,那就将A序列和B序列长度相等的部分和B序列互换
				for(int i=end+1;i<end+1+bLength;i++){//这样可以将B序列放到应该放的
					temp=t[i];t[i]=t[i-aLength];t[i-aLength]=temp;//位置
				}
				start = start+bLength;//同时A序列的长度减少了,A序列中和B互换的子序列
				aLength = aLength-bLength;//变成要左移的到指定位置的序列
			}
		}
			
		
		return t;
	}