189. 旋转数组

给定一个数组，将数组中的元素向右移动 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) 的原地算法。

---

解题思路

使用例子来说明：

题目要求 将数组 a [ 1,2,3,4,5,6,7 ] 向右旋转 k = 3 次，得到结果 a [ 5,6,7,1,2,3,4 ]；我们可以把它看成将数组a中的两个子数组调换了位置，即 将其看成 子数组换位问题；对于本例题就是将 $a[0:4)$ 和 $a[4:7)$ 的子数组两个子数组调换了位置 ；归纳得 ： 可将本题理解为 交换 $a[0:数组长度-k)$ 和 $a[数组长度-k:数组长度）$两个子数组 那怎么 换位两个子数组呢？通过三次逆置数组即可逆置 $a[0:4)$ 子数组 逆置 $a[4:7)$ 子数组 逆置整个数组 $a[0:7)$ 即可得到翻转的值 则最终就是 m = nums.length - k ; inversion(nums, 0, m); inversion(nums, m, nums.length); inversion(nums, 0, nums.length); //inversion(int[]nums ,int l,int r ) 逆置 nums 数组中 下标在 [ l ,r ) 范围中的元素

但是出现这样的测试用例

数组为 a [ -1 ] 移动次数 k = 2对于这个测试用例，得到的 m 为 -1，上面的方法就会报错所以将 k 对 数组长度取余即可得到： class Solution { public void rotate(int[] nums, int k) { k = nums.length - k % nums.length; inversion(nums, 0, k); inversion(nums, k, nums.length); inversion(nums, 0, nums.length); } //逆置 nums 数组中 下标在 [ l ,r ) 范围中的元素 private void inversion(int[] nums, int l, int r) { int half = (l + r) / 2; int temp; for (int i = l; i < half; i++) { temp = nums[i]; nums[i] = nums[r - i + l - 1]; nums[r - i + l - 1] = temp; } } }

优秀的人

class Solution { /** * 双重循环 * 时间复杂度：O(kn) * 空间复杂度：O(1) */ public void rotate_1(int[] nums, int k) { int n = nums.length; k %= n; for (int i = 0; i < k; i++) { int temp = nums[n - 1]; for (int j = n - 1; j > 0; j--) { nums[j] = nums[j - 1]; } nums[0] = temp; } } /** * 翻转 * 时间复杂度：O(n) * 空间复杂度：O(1) */ public void rotate_2(int[] nums, int k) { int n = nums.length; k %= n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } private void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start++] = nums[end]; nums[end--] = temp; } } /** * 循环交换 * 时间复杂度：O(n) * 空间复杂度：O(1) */ public void rotate_3(int[] nums, int k) { int n = nums.length; k %= n; // 第一次交换完毕后，前 k 位数字位置正确，后 n-k 位数字中最后 k 位数字顺序错误，继续交换 for (int start = 0; start < nums.length && k != 0; n -= k, start += k, k %= n) { for (int i = 0; i < k; i++) { swap(nums, start + i, nums.length - k + i); } } } /** * 递归交换 * 时间复杂度：O(n) * 空间复杂度：O(n/k) */ public void rotate(int[] nums, int k) { // 原理同上 recursiveSwap(nums, k, 0, nums.length); } private void recursiveSwap(int[] nums, int k, int start, int length) { k %= length; if (k != 0) { for (int i = 0; i < k; i++) { swap(nums, start + i, nums.length - k + i); } recursiveSwap(nums, k, start + k, length - k); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }