Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Note:
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
如何旋转，这里提供了一个思路，即：
BA=(A'B')'
// 解法一
func rotate(nums []int, k int) {
length := len(nums)
if length == 0 {
return
}
k %= length
for i := 0; i < k; i++ {
temp := nums[length-1]
for j := length - 2; j >= 0; j-- {
nums[j+1] = nums[j]
}
nums[0] = temp
}
}// 解法二
// 这里涉及到一个切片作为参数，如何修改元素的问题，直接修改了便是了
// 可以将切片理解为一个mallock出来的一个堆内存，即便复制了，这个堆内存还是共享的
func rotate(nums []int, k int) {
reverse := func(a []int, start, end int) {
for i, j := start, end; i < j; i, j = i+1, j-1 {
a[i], a[j] = a[j], a[i]
}
}
length := len(nums)
if length == 0 {
return
}
k = k % length
reverse(nums, 0, length-k-1)
reverse(nums, length-k, length-1)
reverse(nums, 0, length-1)
}