来源：LeetCode
难度：中等
描述：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
分析：题意是要将一维数组中的元素进行移位，其中k代表每个元素移动的步数，当k等于数组大小时，相当于没有移动，大于数组大小相当于重新开始移动一步，即咱们可以只考虑移动步数小于n，我们可以把数组分为两截，一截是后面k个元素，一截是前面n-k个元素，最终的目的就是将后面k个按顺序放到前面去，我们可以采用顺序遍历、辅助空间、翻转等方法来解题，如下
题外话：采用额外空间的方式解题简直不要太爽
解题
方法一：顺序移动法
思路：将数组中每个元素按照题意的方式移动k(k=k%n)步，注意最后一个元素的保存以及对第一个元素的替换
代码：
1public void rotate(int[] nums, int k) {
2 int n = nums.length;
3 k = k % n;
4 for(int i = 0; i < k; i ++){
5 //先保留最后一个元素
6 int temp = nums[n - 1];
7 //不断用前一个覆盖后一个
8 for(int j = n - 2; j >= 0; j --){
9 nums[j + 1] = nums[j];
10 }
11 //将第一个元素替换为最后一个
12 nums[0] = temp;
13 }
14}时间复杂度：O(n2)
空间复杂度：O(1)
方法二：辅助空间法
思路：辅助空间也可分为两种方法，一种是申请和原数组一样大小的辅助数组，然后将从k(k=k%n)到n之间的数据先放入辅助数组，然后将0到k之间的数据再放入辅助数组，只有整体替换即可，还有一种是申请k个元素的辅助数组，然后将n-k 到n之间的数据放入辅助数组，0到n-k之间的数据整体向后移k步，最后将辅助空间的数据放入数组头部即可，这里将第二种方式实现下
代码：
1public void rotate(int[] nums, int k) {
2 int length = nums.length;
3 int copyLen = k % length;
4 if (copyLen == 0) {
5 return;
6 }
7 //将后半截k个元素复制下来
8 int[] copy = Arrays.copyOf(nums, copyLen);
9 for (int i = length - 1; i >= 0; i--) {
10 // 0到copyLen 之间的元素向后移k步
11 // i+k 的位置保存的是原来的i的数值
12 nums[(i + copyLen) % length] = nums[i];
13 }
14 //这时候，0-copyLen位置的数据，向后移动了k一部分位置。
15 for (int i = 0; i < copyLen; i++) {
16 nums[(i + copyLen) % length] = copy[i];
17 }
18}
时间复杂度：O(n)
空间复杂度：O(k)
方法三：翻转法
思路：先反转全部数组，在反转前k个，最后在反转剩余的，如下图
代码：
1public void rotate(int[] nums, int k) {
2 int length = nums.length;
3 k %= length;
4 //先反转全部的元素
5 reverse(nums, 0, length - 1);
6 //在反转前k个元素
7 reverse(nums, 0, k - 1);
8 //接着反转剩余的
9 reverse(nums, k, length - 1);
10}
11
12//把数组中从[start，end]之间的元素两两交换,也就是反转
13public void reverse(int[] nums, int start, int end) {
14 while (start < end) {
15 int temp = nums[start];
16 nums[start++] = nums[end];
17 nums[end--] = temp;
18 }
19}
时间复杂度：O(n)
空间复杂度：O(1)
方法四：原地循环替换法
思路：咱们将第一个元素移到第k(k=k%n)位上，将第k位的移动到第(k+k)%n上…，依次类推，当咱们将每个元素都替换一遍后，即完成整个数组的旋转，其中标记数组可以用计数的方式替代，此处用数组标记更清晰易懂
代码：
1public static void rotate(int[] nums, int k) {
2 //保存将要被覆盖的元素
3 int pre = nums[0];
4 int index = 0;
5 int length = nums.length;
6 //利用数组标记该元素是否移动过
7 boolean[] visited = new boolean[length];
8 for (int i = 0; i < length; i++) {
9 index = (index + k) % length;
10 if (visited[index]) {
11 //如果访问过，我们直接从他的下一个元素开始
12 index = (index + 1) % length;
13 pre = nums[index];
14 i--;
15 } else {
16 //修改标记
17 visited[index] = true;
18 //元素交换
19 int temp = nums[index];
20 nums[index] = pre;
21 pre = temp;
22 }
23 }
24}时间复杂度：O(n)
空间复杂度：O(n) n为标记数组
以上仅是个人思路解法
转载请注明：XAMPP中文组官网 » 数组篇3_旋转数组解法思路