力扣每日一题-旋转数组（189）

题目

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

进阶：

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

示例 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）使用额外的数组,使用公式将遍历到的当前数放到另一个数组的对应n的索引位置，公式为’’(i+k)%n’’其中i为当前索引值，k为题目中移动的位置数，n为整个数组的长度。不过此算法的缺点就是用了额外的数组，空间复杂度为O(n),效果不好。

var rotate = function(nums, k) {
     let newNums = new Array();
     let length = nums.length;
     for(i=0;i<length;i++){
         newNums[(i+k)%length] = nums[i]
     }
     for(j=0;j<newNums.length;j++){
         nums[j]= newNums[j]
     }

 return nums
};

（2）数组翻转

该方法基于如下的事实：当我们将数组的元素向右移动 k次后，尾部 k mod n个元素会移动至数组头部，其余元素向后移动 k mod n 个位置。

该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 k mod n个元素就被移至数组头部，然后我们再翻转[0,k mod n−1] 区间的元素和[k mod n,n−1] 区间的元素即能得到最后的答案。

我们以 n=7，k=3 为例进行如下展示：
操作 结果
原始数组 1 2 3 4 5 6 7
翻转所有元素 7 6 5 4 3 2 1
翻转 [0,k mod n−1] 区间的元素 5 6 7 4 3 2 1
翻转 [k mod n,n−1] 区间的元素 5 6 7 1 2 3 4

var reverse = function(arr,start,end){
    while(start<end){
        let temp
        temp = arr[end]
        arr[end] = arr[start]
        arr[start] = temp
        start++
        end--
    }
}
var rotate = function(nums, k) {
    let len = nums.length
    let mid = k%len
    reverse(nums,0,len-1)
    reverse(nums,0,mid-1)
    reverse(nums,mid,len-1)
return nums
};

(3)做k次循环，每次将nums数组结尾元素通过unshift（）方法插入到nums开头，pop方法删除结尾元素,其实就是做了一个队列的作用。（这个方法真是绝了，对于javascript语言简直来说是超级简单了，也没有用到其他的内存，不过其他的语言不好说，这里使用了javascript自备的一些api函数）

var rotate = function(nums, k) {
    let len = nums.length
    for(let i=0;i<k%len;i++){
        nums.unshift(nums[nums.length-1]);
        nums.pop();
    }
};

(4)如 nums = [1,2,3,4,5,6,7], k = 3,截取后面k个, 放到开头[5,6,7] 此时nums = [1,2,3,4]再放回去[5,6,7,1,2,3,4],但算是用到了额外的空间。

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

还有一种环状替换没怎么看懂，先放放吧！！