# 189. 旋转数组

# 题目

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

例

输入: [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]

说明:

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

# 题解

# 直接替换

每个元素的新位置是 (i+K)%l

i 是当前位置
K 是向右移动位置
l 是数组长度

用一个中间变量保存被替代

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  const l = nums.length;
  k = k % l;
  let c = 0;
  for (let i = 0; c < l; ++i) {
    let cur = i;
    let pre = nums[i];
    do {
      let next = (cur + k) % l; // 下一个位置
      let tmp = nums[next]; // 先缓存要换位的值
      nums[next] = pre; // 换位
      pre = tmp; // 缓存的值是下一个要交换的值
      cur = next; // 替换索引
      c++;
    } while (i != cur);
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度： O(n)

空间复杂度： O(1)

# 模拟操作

右移就是出栈入队

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  while (k > 0) {
    let x = nums.pop();
    nums.unshift(x);
    k--;
  }
};

1
2
3
4
5
6
7
8
9
10
11
12

# 反转

原始数组 :            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 --> 结果

1
2
3
4

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
};

function reverse(nums, i, j) {
  for (; i < j; i++, j--) {
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：三次反转 O(n)

空间复杂度： O(n)

← 172. 阶乘后的零 191. 位 1 的个数 →