3 - Easy-旋转数组

将包含n个元素的数组向右旋转k步。

例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

注意:

尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。

要求空间复杂度为 O(1)

将前n-k个原地反转，将后k个原地反转，再将整个数组原地反转，即得所求。【时间复杂度O(n)，空间复杂度O(1)】

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.
        """
        k = k % len(nums)
        self.reversePart(nums, 0, len(nums)-k-1)
        self.reversePart(nums, len(nums)-k, len(nums)-1)
        self.reversePart(nums, 0, len(nums)-1)

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

空间复杂度为O(1)，我们可能会想到对原数组做k次“循环右移一位”的解法。然而直接这么做会超时，所以可以考虑下面的优化做法。其思想是，每次把数组最后k位交换到正确的位置，循环直到所有元素位置正确。

class Solution:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k, start, n = k % len(nums), 0, len(nums)
        while k % n != 0 and n > 0:
            for i in range(k):
                nums[start + i], nums[len(nums) - k + i] = nums[len(nums) - k + i], nums[start + i]
            start, n = start + k, n - k
            k = k % n