前言

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

示例 1:

  1. 输入: [1,2,3,4,5,6,7] 和 k = 3
  2. 输出: [5,6,7,1,2,3,4]
  3. 解释:
  4. 向右旋转 1 步: [7,1,2,3,4,5,6]
  5. 向右旋转 2 步: [6,7,1,2,3,4,5]
  6. 向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

  1. 输入: [-1,-100,3,99] 和 k = 2
  2. 输出: [3,99,-1,-100]
  3. 解释: 
  4. 向右旋转 1 步: [99,-1,-100,3]
  5. 向右旋转 2 步: [3,99,-1,-100]

说明:

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

解决方案

提示

在解题之前，我们首先要确定一些异常情况，比如数组的长度为0，以及旋转的长度大于数组长度的情况。
其中如果旋转的长度大于数组

方案一 ：利用额外的数组，然后进行旋转，空间复杂度o(n),时间复杂度o(n)

解题思路：将原来的数组进行备份，然后将数组的赋值按照传入的参数分为两部分，左边为原来分割的右部分；右边为分割的左部分，思路比较顺畅简单。需要注意的是：当传入的旋转度为len的时候相当于不旋转，当旋转度大于len的时候，和k-len的效果是相同的(len为数组长度)。

  1. * @param {number[]} nums
  2.  * @param {number} k
  3.  * @return {void} Do not return anything, modify nums in-place instead.
  4.  */
  5. var rotate = function(nums, k) {
  6.    let len = nums.length
  7.   if(len ===0 || k ===0 || k===len ){return} 
  8.   if(k>len){k=k-len}
  9.   let numsCp = [...nums]
  10.   for(let i=0;i<len;i++){
  11.     if(k>i){
  12.        nums[i] = numsCp[(len-k+i)%len]
  13.     }else{
  14.        nums[i] = numsCp[i-k]
  15.     }
  16.   }     
  17. };

方案二 ：每次移动一个元素，将其他元素后移动，移动k次，空间复杂度o(1),时间复杂度o(n^2)

  1. var rotate = function(nums, k) {
  2.     let len = nums.length
  3.    if(!k || k===len){
  4.     return
  5.   }
  6.  if(k>len){k=k-len}
  7.   for(let i =0 ;i<k;i++){
  8.     let temp = nums[len-1]
  9.     for(let j=len-1;j>0;j--){
  10.       nums[j] = nums[j-1]
  11.     }
  12.     nums[0] =temp
  13.   }    
  14. };

方案三 ：数组旋转看成分割后数组的翻转，然后再整体数组翻转，空间复杂度o(1),时间复杂度o(3n)

  1. var rotate = function(nums, k) {
  2.     let len = nums.length
  3.    if(!k || k===len){
  4.     return
  5.   }
  6.   if(k>len){k=k-len}
  7.   let reverse = (arr,i,k)=>{
  8.     if(k==1) return 
  9.     for(let j=0;j<Math.floor(k/2);j++){
  10.       let temp =arr[i+k-j-1]
  11.        arr[i+k-j-1] = arr[i+j]
  12.        arr[i+j] = temp
  13.     }
  14.   }
  15.   reverse(nums,0,len-k)
  16.   reverse(nums,len-k,k)
  17.   reverse(nums,0,len)   
  18. };

方案四 ：借用临时变量将需要旋转的n个元素旋转即可，空间复杂度o(n),时间复杂度o(1)

方案五 ：借用临时数组，删除并保留数组元素即可