189. Rotate Array

这一题想到一个只用一个额外空间的办法，但是超时了

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.
        """
        n = len(nums) 
        k = k % n
        for i in range(k,0,-1):
            temp = nums[n-i]
            for j in range(n-i-1, k-i-1, -1):
                nums[j+1] = nums[j]
            nums[k-i] = temp

AC的做法：

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.
        """
        n = len(nums) 
        k = k % n
        temp = []
        for i in range(n-k, n):
            temp.append(nums[i])
        for j in range(n-k-1,-1,-1):
            nums[j+k] = nums[j]
        for i in range(k):
            nums[i] = temp[i]

巧妙的做法，按照K将数组分成两部分，两部分分别reverse，注意这里没办法用函数，需要按照坐标reverse，要注意下标，最后合起来再reverse，这里可以直接用reverse函数，代码如下：

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.
        """
        n = len(nums) 
        k = k % n
        for i in range((n-k)/2): 
            nums[i], nums[n-k-1-i] = nums[n-k-1-i], nums[i]
        for j in range(n-k,n - k + k/ 2):
            nums[j], nums[2*n-k-1-j] = nums[2*n-k-1-j], nums[j]
        nums.reverse()