Rotate Array

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

For example, withn= 7 andk= 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?

Related problem:Reverse Words in a String II

三步翻转法

1. reverse the first n - k elements

2. reverse the rest of them

3. reverse the entire array

O(n) in time, O(1) in space

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        l = len(nums)
        k = k % l
        self.reverse(nums, 0, l - k - 1)
        self.reverse(nums, l - k, l - 1)
        self.reverse(nums, 0, l - 1)

    def reverse(self, nums, start, end):
        while start < end:
            temp = nums[start]
            nums[start] = nums[end]
            nums[end] = temp
            start += 1
            end -= 1

剩下解法：

https://discuss.leetcode.com/topic/47235/summary-of-solutions-in-python

http://bookshadow.com/weblog/2015/02/24/leetcode-rotate-array/

For reversing the same list use:

array.reverse()    #Here array will be reversed in-place (no new list made)

To assign reversed list into some other list use:

newArray = array[::-1]