数组元素的处理问题，大家或多或少都有听说过，例如今天要讲的就是数组元素整体移动问题。
将数组元素整体平移，例如整体向左平移3个单位或者整体向右平移4个单位。举一个例子，现在有一个数组为[1,2,3,4,5]，整体向左平移3个单位以后得到的数组为[4,5,1,2,3]；反过来，如果将其整体向右平移4个单位，得到的新数组是[2,3,4,5,1]。这就是数组整体移动问题。
本文我们假定整体向右平移，因为向左平移原理类似，程序稍作修改即可。
那么对于一个长度为N的数组A，将其整体向右平移K个单位，在计算机程序设计上应该如何实现呢？
第一种思想：新建一个数组，赋值即可
大家可能最容易想到的一种算法就是，新建一个和数组A具有相同维度的数组B，然后从数组A的第（N-K-1）个元素（元素下标从0开始）开始赋值给数组B的第0个元素，直到数组A的末尾元素，然后回过头把A的前（N-K）个元素依次赋给数组B。这样，最终就满足了问题要求，使得B数组为A数组整体向右平移K个单位后的结果。
算法理解清楚了，这种解决方案用程序表达出来也就很轻松了，下面就给出使用Java编写的第一种算法。这种算法的空间复杂度为O(N)，时间复杂度也为O(N)。
/**
* 最朴素的算法，开辟另一个数字，拷贝进去就是了
* @param a 输入数组
* @param k 移动步数
* 时间复杂度 O(N)
* 空间复杂度 O(N)
*/
public static void rotate1(int[] a,int k) {
int[] b = new int[a.length];
for(int i=0;i<k;i++) {
b[i]=a[a.length-k+i];
}
for(int j=0;j<a.length-k;j++) {
b[j+k]=a[j];
}
System.arraycopy(b, 0, a, 0, a.length);
}
第二种思想：巧妙借助冒泡排序的方式
在【AD1】中我有讲过6中经典的排序算法以及实现代码（没看过的朋友可以翻阅公众号的历史文章），其中提到了一种常见的排序算法——冒泡排序。冒泡排序的思想很简单，即两两比较，使得每次遍历数组以后都可以使得某个最大或者最小元素“浮出”数组，看起来好像鱼在水里呼吸冒泡上浮，因此叫做冒泡排序算法。那么这里，我们也可以类似思考，例如数组从[1,2,3,4,5]向右平移3个单位，变成[3,4,5,1,2]，相当于元素3,4,5依次向上冒泡，而1,2自然被沉入底部。
这里的冒泡相比冒泡排序会更加简单，原因是冒泡排序中还要对数组的相邻元素进行比较，再确定哪个元素上浮，而这里呢，我们只用从元素3开始，两两交换使得3上浮，同时1,2整体下沉一格；然后再从元素4开始，两两交换使得4上浮，同时1,2继续整体下沉一格；最后从元素5开始，两两交换使得5上浮，同时1,2继续整体下沉至数组底部。
下面用简洁的代码来说明上述冒泡算法。这种算法的时间复杂度为O(N*K），空间复杂度为O（1）。
/**
* 想到冒泡排序算法的思想
* @param a 输入数组
* @param k 移动步数
* 时间复杂度 O(N*k)
* 空间复杂度 O(1)
*/
public static void rotate2(int[] a,int k) {
for(int i=0;i<k;i++) {
for(int j=a.length-k+i;j>i;j--) {
int tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
}
}
第三种思想：旋转的思维
这种旋转思维需要我们敏锐的观察能力，如数组[1,2,3,4,5]是如何变成数组[3,4,5,1,2]的呢？从外观上来看，我们可以发现变化过程可以是这样的：
首先将数组分成两大块，分别是[1,2]和[3,4,5]；
然后对数组[1,2]进行颠倒，即变成了[2,1]；
然后对数组[3,4,5]也进行颠倒，即变成了[5,4,3]；
然后将两个数组拼接起来，得到[2,1,5,4,3]；
最后对上面的数组[2,1,5,4,3]进行颠倒，即可得到[3,4,5,1,2]，算法结束。
这是一种很巧妙的算法，其时间复杂度为O（N），空间复杂度为O（1）。下面给出简洁的实现代码，对一个数组如何进行颠倒实现起来很简单，这里就不再详细说明了。
/**
*
* @param a 输入数组
* @param k 移动步数
* 时间复杂度 O(N)
* 空间复杂度 O(1)
*/
public static void rotate3(int[] a,int k) {
reverse(a,0,a.length-k-1);
reverse(a,a.length-k,a.length-1);
reverse(a,0,a.length-1);
}
public static void reverse(int[]a,int start,int end) {
for(int i=0;i<(end-start+1)/2;i++) {
int tmp=a[start+i];
a[start+i]=a[end-i];
a[end-i]=tmp;
}
}
最后分享名句：
拥抱生活的人，生活也拥抱他。远离生活的人，生活也远离他。
来源：张泽旺 深度学习每日摘要
智造家
