题目

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

Example 1:

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

Example 2:

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

Note:

  • 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?

题意

将给定数列的指定后半部分与前半部分换位，得到新数组。

思路

最经典的0189. Rotate Array (E) - 图1空间方法是翻转法：先将左子数组翻转，再将右子数组翻转，最后将整个数组翻转，得到的就是目标数组。

比较直接的是按照步骤一个一个移动元素，或者使用额外数组先将右子数组保存下来再处理。

官方解答还提供了一种循环替换法：以一个元素为起点，直接将该元素放在它应在的位置上，并将该位置上原本的元素继续按上述操作放在下一个位置上，直到回到起点完成一次循环，接着更换起点重复操作即可。当这种放置进行了n次后，所有元素都已经在它应在的位置上。该方法是对暴力法的一种优化。

代码实现

Java

翻转法

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         k = k % nums.length;
  4.         reverse(nums, 0, nums.length - 1 - k);
  5.         reverse(nums, nums.length - k, nums.length - 1);
  6.         reverse(nums, 0, nums.length - 1);
  7.     }
  9.     private void reverse(int[] nums, int left, int right) {
  10.         while (left < right) {
  11.             int temp = nums[left];
  12.             nums[left] = nums[right];
  13.             nums[right] = temp;
  14.             left++;
  15.             right--;
  16.         }
  17.     }
  18. }

暴力法

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         for (int i = 0; i < k; i++) {
  4.             int pre = nums[nums.length - 1];
  5.             for (int j = 0; j < nums.length; j++) {
  6.                 int temp = nums[j];
  7.                 nums[j] = pre;
  8.                 pre = temp;
  9.             }
  10.         }
  11.     }
  12. }

额外数组

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         k = k % nums.length;
  4.         int[] temp = Arrays.copyOfRange(nums, nums.length - k, nums.length);
  5.         for (int i = nums.length - 1; i >= k; i--) {
  6.             nums[i] = nums[i - k];
  7.         }
  8.         for (int i = 0; i < k; i++) {
  9.             nums[i] = temp[i];
  10.         }
  11.     }
  12. }

循环替换

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         k = k % nums.length;
  4.         int count = 0;
  6.         // 当count==nums.length时，说明所有元素都已经在它应在的位置上
  7.         for (int i = 0; count < nums.length; i++) {
  8.             int j = i;
  9.             int pre = nums[j];
  10.             do {
  11.                 int next = (j + k) % nums.length;
  12.                 int temp = nums[next];
  13.                 nums[next] = pre;
  14.                 pre = temp;
  15.                 j = next;
  16.                 count++;
  17.             } while (j != i);    // 回到起点，说明一次循环完成
  18.         }
  19.     }
  20. }

JavaScript

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {void} Do not return anything, modify nums in-place instead.
  5.  */
  6. var rotate = function (nums, k) {
  7.   k %= nums.length
  8.   nums
  9.     .slice(0, nums.length - k)
  10.     .reverse()
  11.     .concat(nums.slice(nums.length - k).reverse())
  12.     .reverse()
  13.     .forEach((v, i) => (nums[i] = v))
  14. }