Array - Array Rotation
问题：将一个长度为n的数组中的元素右移k个位置。例如当n=5, k=3时：[1, 2, 3, 4, 5] => [3, 4, 5, 1, 2]。
要求O(1)的空间复杂度。
这个问题通常被别的复杂一些的题解题的时候用到，与之类似的还有链表的 rotation。通常采用整体反转，再局部反转的方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | package mainimport "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)
