题目内容

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 比如，给定数组[1,2,3,4,5]和k为3，应该返回的数组为[3,4,5,1,2]。

解完此题的最大意义不是让我熟悉和掌握了旋转数组的各种方法，而是让我学到了一个新的词原地算法。为什么要提及这个词，在尝试下面所说的第二种解法时，陷入了一个浏览器能返回答案，但是LeetCode就是不给过的问题中。

我跟代码交流的原则一直是：如果有问题，先重试一遍，如果仍然出现，必须乖乖认错。但是这情况就傻眼了，浏览器和LeetCode竟然没有返回一致的答案。有点三体中基础物理失效的感觉。

当时没有细看题目的说明，补充如下。

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

两条都是非常常规而普通的要求，以至于被我瞥一眼忽略了。在第二条中，有一个词是原地算法。当时不以为意，管你什么算法，能抓到老鼠就是好猫。没想到抓了只蝙蝠。

题目要求至少三种不同解法，虽然题目看着简单。但老实说一开始我并没有想出三种，两种分别是：

• pop方法和unshift方法结合，用队列的思想，出队一个就再让它进队。
• 数组的splice方法和concat方法，剪切需要翻转的部分并拼接。

---

解法一，pop跟unshift结合

这个思路应该很容易想到，代码逻辑和实现上都比较简单。

var rotate = function(nums, k) {
    let len = nums.length
    let convert = function (arr) {
        let temp = arr.pop()
        arr.unshift(temp)
    	k -=1
        return arr
    }
    while (k > 0) {
        convert(nums)
    }
};

不过在题解区看到了这个思路更简化的写法，判断了边界条件让一些测试用例可以更快通过；此外，优化掉了我用到的那个temp临时变量。

  let len = nums.length
  if (len < 2) {
    return
  }
  if (k < 0) {
    return
  }

  while (k--) {
    nums.unshift(nums.pop())  
  }

---

方法二，splice 和 concat

这个方法也不难，大思路还是跟方法一一样，都是把后面的元素挪到前面，只是在实现细节上不一样。

先看无论如何LeetCode也不会让我过的代码。具体实现上，先根据传入的k确定需要取出的数组部分。车就翻在第二个语句。

在分析问题为什么会出现之前，先来了解什么叫“原地算法”。

在计算机科学中，一个原地算法（in-place algorithm）基本上不需要额外辅助的数据结构,然而,允许少量额外的辅助变量来转换数据的算法。当算法运行时，输入的数据通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。 --- 维基百科

简单来说，我的理解就是要完成的操作都是对于当前数组而不需要借助别的数组，即改变原数组自己。

回到下面的代码中，第二个语句使用了concat方法，而concat并不会改变原数组，而是返回一个拼接过的新数组。这也回应了写代码LeetCode自动生成的注释。

Do not return anything, modify nums in-place instead.

所以在第二句中，即便我把concat方法返回的数组赋值给了nums。但此时，虽然结果看着是一样的，但nums数组原有引用地址已经变了。又传入的nums地址变为concat返回的那个地址。所以，不管代码中最后return的是啥，LeetCode测试结果只会追踪最开始传入nums引用地址的元素变动情况。

这也是我提交这代码后，提交结果显示我的答案是nums数组被剪切后剩下的部分的原因。

var rotate = function(nums, k) {
    let arr = nums.splice(nums.length - k, nums.length)
    nums = arr.concat(nums)
}

由此，如果一定要用splice的话，就只能用unshift将其挨个推入原数组前面。不过这就没那么优雅了。

var rotate = function(nums, k) {
    let arr = nums.splice(nums.length - k, nums.length)
    while (arr.length > 0) {
        nums.unshift(arr[arr.length - 1])
        arr.length -= 1
    }
    return nums
};

---

方法三，巧用splice

对于splice，我们更熟悉的应该是他的删除能力，但其实splice也可以实现对数组在指定位置的元素添加操作。但因为里面的splice剪切出来的仍然是一个数组，所以需要用到...拓展操作符将其转为可直接放进数组中的元素。

var rotate = function(nums, k) {
    nums.splice(0, 0, ...nums.splice(nums.length - k, nums.length))
};

展开语法(Spread syntax), 可以在函数调用/数组构造时, 将数组表达式或者string在语法层面展开；还可以在构造字面量对象时, 将对象表达式按key-value的方式展开。