目录

1，题目描述

英文描述

中文描述

2，解题思路

方法一：环状替换

方法二：反转

3，AC代码

方法一：环状替换

C++

Java

方法二：反转

C++

4，解题过程

第一博

第二搏

第三搏

---

1，题目描述

原题链接189. 旋转数组；

虽说是简单题，但是算法还是很巧妙的！

英文描述

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem. Could you do it in-place with O(1) extra space?  

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation:  rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]  

Constraints:

1 <= nums.length <= 2 * 10^4 It's guaranteed that nums[i] fits in a 32 bit-signed integer. k >= 0

中文描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4] 示例 2:

输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释:  向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100] 说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 要求使用空间复杂度为 O(1) 的 原地 算法。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotate-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2，解题思路

参考@力扣 (LeetCode)【旋转数组】

方法一：环状替换

通过观察交换位置的坐标关系，可以发现：

每将一个元素放入到最终位置时，可以得到下一个元素以及该元素的最终位置，以此类推，通过类似于一个环状替换的过程，可以将该环中涉及到的元素放置在最终位置上；

通过交换的次数来判断算法是否完成（交换次数count==数组长度时，算法完成）；

若一个环遍历完毕，且算法未结束，说明还存在其他的环，所以调整下一个环开始的位置（从0开始递增即可），继续进行环状替换；

方法二：反转

原始数组                          : 1 2 3 4 5 6 7

反转所有数字后               : 7 6 5 4 3 2 1

反转前 k 个数字后           : 5 6 7 4 3 2 1

反转后 n-k 个数字后        : 5 6 7 1 2 3 4 --> 结果

3，AC代码

方法一：环状替换

C++

class Solution { public: void rotate(vector<int>& nums, int k) { k = k % nums.size(); // 对k取模 int count = 0; // 记录交换的次数 此算法保证只遍历一次数组即可 for(int start = 0; count < nums.size(); start++) { int current = start; int prev = nums[start], next; // prev存放即将替换的元素 next标明替换的位置 do { next = (current + k) % nums.size(); swap(prev, nums[next]); // 每次循环 prev都将得到一个放入下一位置的元素 current = next; count++; }while(current != start); } } };

Java

class Solution { public void rotate(int[] nums, int k) { int count = 0; for(int start = 0; count < nums.length; start++) { int current = start, next = 0; int prev = nums[current]; do { next = (current + k) % nums.length; int tem = nums[next]; nums[next] = prev; prev = tem; count++; current = next; }while(current != start); } } }

方法二：反转

C++

class Solution { public: void rotate(vector<int>& nums, int k) { k = k % nums.size(); reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() + k); reverse(nums.begin() + k, nums.end()); } };

4，解题过程

第一博

一开始，针对给出的样例，手动写了交换元素间的坐标位置关系：0-3，0-6，0-2，0-5，0-1，0-4，这样7个元素，交换六次就可以实现。然而前提是只有一个环，有的用例含有多个环，上述解法就需要动态修改一些边界，很容易出错。

 

第二搏

参考官网给出的解法，其中解法三和我的思路很像，只不过采用变量prev保存将要交换的元素，并且利用count计数，这样可以保证每个位置都交换一次。

一旦当前位置和起始位置重合，开始循环下一个环

通过记录 交换的次数 来判断算法是否终止，这样可以实现多个环的交换。

时间O(N)，空间O(1)，只遍历一次数组；

第三搏

另一种方法是，将整个数组前后对调，再将前k个元素和剩余的元素分别对调，这样即可得到最终答案，相当于完整遍历了两次数组；

时间O(N)，空间O(1)；