20170607-leetcode-189-Rotate Array

1.Description

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.

[show hint]

Related problem: Reverse Words in a String IIRotate 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.

[show hint]

Related problem: Reverse Words in a String II 解读 把list（或者array）看成是一个环，求向右转动k个数之后的list 比如1,2,3,4,5,6,7，想象7指向1：

向右移动1，结果为：7,1,2,3,4,5,6 向右移动2，结果为：6,7,1,2,3,4,5 向右移动3，结果为：5,6,7,1,2,3,4

2.Solution

2.1找到分界点,断开，重新组合，给list重新赋值

class Solution(object): def rotate(self, nums, k): n = len(nums) k = k % n nums[:] = nums[n-k:] + nums[:n-k] #或者简写成下面的形式： def rotate(self, nums, k): k = k % len(nums) nums[:] = nums[-k:] + nums[:-k]

注：最后的写成是num[:]而不是num的原因是，用num进行赋值会改变原来的值，而num[:]只是修改指针，效率更高

2.2

以n - k为界，分别对数组的左右两边执行一次逆置；然后对整个数组执行逆置。

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

2.3不断移动元素进行实现

将数组元素依次循环向右平移k个单位

class Solution: 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]

2.4数组(list)长度加倍，截断

class Solution(object): def rotate(self, nums, k): n=len(nums) k = k % n nums[:]=(nums*2)[n-k:2*n-k]

2.5下面一种方式超时

def rotate(self, nums, k): k = k % len(nums) for i in range(k): nums[:] = [nums[-1]] + nums[:-1]