189. 轮转数组

189. 轮转数组

力扣题目链接[1]

给你一个数组，将数组中的元素向右轮转 k个位置，其中k是非负数。

示例1：

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

「提示：」

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

「进阶：」

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

思路：

首先想到的就是依次将数组末尾的数字弹出，同时放入数组头部，可以写出如下代码：

pop+unshift

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const length = nums.length;
    if (!k || !length) return nums;
    const step = Math.abs(k % length);
    for (let i = 0; i < step; i++) {
        nums.unshift(nums.pop());
    }
    return nums;
};

不幸的是，此方法会超时。因为频繁的弹出和头部插入，会使得数组不断的挪动元素来腾出位置给头部插入的元素。

splice

本题的难点在于原地修改。如果没有该限制，便可以使用slice进行截取，拼接新数组进行返回即可。

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

这里使用splice来实现原地修改。首先来复习下splice的用法：

「splice()」 方法通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组。接受三个参数，分别是：

• start。指定修改的开始位置（从0计数）。如果超出了数组的长度，则从数组末尾开始添加内容；如果是负值，则表示从数组末位开始的第几位（从-1计数，这意味着-n是倒数第n个元素并且等价于array.length-n）；如果负数的绝对值大于数组的长度，则表示开始位置为第0位。
• deleteCount(可选)。整数，表示要移除的数组元素的个数。如果 deleteCount 大于 start 之后的元素的总数，则从 start 后面的元素都将被删除（含第 start 位）。如果 deleteCount 被省略了，或者它的值大于等于array.length - start(也就是说，如果它大于或者等于start之后的所有元素的数量)，那么start之后数组的所有元素都会被删除。如果 deleteCount 是 0 或者负数，则不移除元素。这种情况下，至少应添加一个新元素。
• item1, item2, ...(可选)。要添加进数组的元素,从start 位置开始。如果不指定，则 splice()将只删除数组元素。

返回值：由被删除的元素组成的一个数组。如果只删除了一个元素，则返回只包含一个元素的数组。如果没有删除元素，则返回空数组。

因此，我们需要做的就是删除后面k个元素，同时添加进数组头部。删除后面k个元素，可以通过nums.splice(length - k)实现。删除后会返回被删除元素组成的数组，此时需要插入到数组的头部。因为第三个参数可接收多个值，因此这里通过展开运算符将被删除元素组成的数组展开，从0位置开始，插入到数组中。

总结

本题的难点在于原地修改数组，因此这里使用了数组APIsplice来原地修改。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/problems/rotate-array/