## 题目描述：

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint:

Could you do it in-place with O(1) extra space?

## 解题思路及代码：

### 解法一 [ 时间复杂度O（n），空间复杂度O(1) ]：

```reverse(nums, 0, n - k - 1)
reverse(nums, n - k, n - 1)
reverse(nums, 0, n - 1)```

### Python代码：

``````class Solution:
# @param nums, a list of integer
# @param k, num of steps
# @return nothing, please modify the nums list in-place.
def rotate(self, nums, k):
n = len(nums)
k %= n
self.reverse(nums, 0, n - k)
self.reverse(nums, n - k, n)
self.reverse(nums, 0, n)

def reverse(self, nums, start, end):
for x in range(start, (start + end) / 2):
nums[x] ^= nums[start + end - x - 1]
nums[start + end - x - 1] ^= nums[x]
nums[x] ^= nums[start + end - x - 1]
``````

### 注释：

Python中两个数交换可以用如下方法实现：

`a, b = b, a`

```a ^= b
b ^= a
a ^= b```

### Python代码：

``````class Solution:
# @param nums, a list of integer
# @param k, num of steps
# @return nothing, please modify the nums list in-place.
def rotate(self, nums, k):
n = len(nums)
idx = 0
distance = 0
cur = nums[0]
for x in range(n):
idx = (idx + k) % n
nums[idx], cur = cur, nums[idx]

distance = (distance + k) % n
if distance == 0:
idx = (idx + 1) % n
cur = nums[idx]
``````

``````class Solution:
# @param nums, a list of integer
# @param k, num of steps
# @return nothing, please modify the nums list in-place.
def rotate(self, nums, k):
n = len(nums)
if k > 0 and n > 1:
nums[:] = nums[n - k:] + nums[:n - k]
``````

Pingbacks已关闭。

1. 爱美的玛丽娜 发布于 2015年11月26日 11:43 #

第二个没看懂...T,T

2. 在线疯狂 发布于 2015年11月26日 23:44 #

nums = [1,2,3,4,5,6,7], k = 3的运行过程中nums和cur的变化过程：
0 -> 3 [1, 2, 3, 1, 5, 6, 7] 4
3 -> 6 [1, 2, 3, 1, 5, 6, 4] 7
6 -> 2 [1, 2, 7, 1, 5, 6, 4] 3
2 -> 5 [1, 2, 7, 1, 5, 3, 4] 6
5 -> 1 [1, 6, 7, 1, 5, 3, 4] 2
1 -> 4 [1, 6, 7, 1, 2, 3, 4] 5
4 -> 0 [5, 6, 7, 1, 2, 3, 4] 1

3. Kevin 发布于 2016年5月13日 15:12 #

class Solution:
# @param nums, a list of integer
# @param k, num of steps
# @return nothing, please modify the nums list in-place.
def rotate(self, nums, k):
n = len(nums)
k = k % n
nums[:] = nums[n-k:] + nums[:n-k]

切片更简洁

4. Nigel 发布于 2016年9月7日 18:35 #

第一种解法，如果K大于字符串的长度，则结果有问题。

5. 在线疯狂 发布于 2016年9月7日 19:57 #

k %= n，这行代码将k限制在字符串长度范围之内