【Leetcode初级算法】3-旋转数组

• 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

• 思路：
  这道题是一道比较经典的题目，网上流传了三种方法，我自己一开始是按照第二种思路来思考这道问题的。
  第一种思路是最基础的，也是复杂度最高的。每次将所有的元素向右移动1位，然后循环K次。这样做时间复杂度O(nk)即O(nn)，我提交到leetcode后，当数组元素出现较多的测试case就超时了。
  这里可优化一点，就是设置K=K%N，因为K若远大于N时，移动K次和移动K-N次是没有区别的，多折腾一个来回。所以取余数来计算。
  这条思路的代码就不贴了，移1位的操作只要设置一个tmp变量保存最后一个值num[n-1]，每前一个值赋给后一个，最后把tmp赋给nums[0]就行。

• 第二种思路，以空间换时间。比如[1,2,3,4,5,6,7]向右移动3步到[5,6,7,1,2,3,4]，可以看成[1,2,3,4]向右移动了3位，然后[5,6,7]向左移动了4位。这样可以把[5,6,7]提前保存在tmp数组里，等[1,2,3,4]移动完后，再将tmp从第一位开始赋值给nums。
  所以先tmp缓存n-k到n-1这k个值，再移动0到n-k-1的值右移k位，最后tmp赋值到nums首位。这样时间复杂度为O(n+k)即O(n)，空间复杂度为O(n)。
  贴上Python代码：

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)
        if n == 0 :
            return
        k = k % n
        tmp = range(n)
        p = 0
        i = n - k
        while i < n:
            tmp[p] = nums[i]
            p += 1
            i += 1
        j = n-k-1
        while j >= 0:
            nums[j+k] = nums[j]
            j -= 1
        x = 0
        while x < k:
            nums[x] = tmp[x]
            x += 1

• 最后还有一种reverse数组的方法，据说速度更快，我还没来得及研究。待续。