Array - Array Rotation
问题：将一个长度为n的数组中的元素右移k个位置。例如当n=5, k=3时：[1, 2, 3, 4, 5] => [3, 4, 5, 1, 2]。
要求O(1)的空间复杂度。
这个问题通常被别的复杂一些的题解题的时候用到，与之类似的还有链表的 rotation。通常采用整体反转，再局部反转的方法。
package main
import "fmt"
func main() {
input := []int{1, 2, 3, 4, 5, 6}
arrayRotation(input, 2)
fmt.Println("after rotation: ", input)
}
func arrayRotation(num []int, k int) {
size := len(num)
for i := 0; i < size/2; i++ {
num[i], num[size-i-1] = num[size-i-1], num[i]
}
for i := 0; i < k/2; i++ {
num[i], num[k-i-1] = num[k-i-1], num[i]
}
i := k
j := size - 1
for i < j {
num[i], num[j] = num[j], num[i]
i++
j--
}
}
评论 (0)
