题目

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

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]

思路 - O(n)空间

涉及到旋转，比如数组的旋转或链表的旋转，多半和取模有关系，需要取模来抵消旋转一周的效果。
关键点在于对 k 大于数组长度的情况的处理。当 k 大于数组长度，k % n是实际的旋转次数。

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         int[] temp = new int[k];
  4.         int n = nums.length;
  5.         int p = 0;
  6.         k %= n;  // 取模使得k <= n. 举例：k = 5，n = 3，5 % 3 = 2，就相当于旋转了2次
  7.         for (int i = n - k; i < n && p < n; i++) {  // 复制要旋转的那段数组到temp
  8.             temp[p] = nums[i];
  9.             p++;
  10.         }
  11.         for (int i = n - k - 1; i >= 0; i--) {  // 移动前半段不用旋转的数组到后半段
  12.             nums[i + k] = nums[i]; 
  13.         }
  14.         for (int i = 0; i < k; i++) {  // 把temp挪到前半段
  15.             nums[i] = temp[i];
  16.         }
  17.     }
  18. }

思路 - O(1)空间

贴一个lc上绝妙的理解：

  1. nums = "----->-->"; k =3
  2. result = "-->----->";
  4. reverse "----->-->" we can get "<--<-----"
  5. reverse "<--" we can get "--><-----"
  6. reverse "<-----" we can get "-->----->"
  7. this visualization help me figure it out :)
  8. https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         k %= nums.length;
  4.         reverse(nums, 0, nums.length - 1);
  5.         reverse(nums, 0, k - 1);
  6.         reverse(nums, k, nums.length - 1);
  7.     }
  9.     public void reverse(int[] nums, int i, int j) {
  10.         while (i < j) {
  11.             int temp = nums[i];
  12.             nums[i] = nums[j];
  13.             nums[j] = temp;
  14.             i++; j--;
  15.         }
  16.     }
  17. }