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]
}
}
