旋转数组

image.png

方法一: 暴力解法

一步一步移动数组,将数组中的每个元素都往后走一步,将末尾的值放到起点
k步后就是想要的结果

func rotate(nums []int, k int)  {
   for i := 0; i < k; i++ {
        r := nums[len(nums)-1]
        for n := len(nums) - 1; n-1 >= 0; n-- {
            nums[n] = nums[n-1]
        }
        nums[0] = r
    }
}

时间复杂度: O(n*k)
空间复杂度: O(1)
没有额外空间被使用。

方法二: 使用额外的数组

计算出旋转后的数字所在的key值
(n+k)%len(nums)

func rotate(nums []int, k int)  {
    var newNums []int
    for n:=range nums{
        newNums = append(newNums,nums[n])
    }
    for n:=range newNums {
        nums[(n+k)%len(nums)] = newNums[n]
    }
    
}

时间复杂度: O(n)
将数字放到新的数组中需要一遍遍历，另一边来把新数组的元素拷贝回原数组。
空间复杂度: O(n)
另一个数组需要原数组长度的空间。

方法三: 环状替换

思路如图

方法四: 反转数组

func rotate(nums []int, k int)  {
    key:=k%len(nums)
    //将数组整个反转
    reverse(nums)
    //以k%len(nums)作为分界,分别反转
    reverse(nums[:key])
    reverse(nums[key:])
}

func reverse(nums []int)  {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}