• 給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。

示例 1:
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

• 思路：
  這道題是一道比較經(jīng)典的題目，網(wǎng)上流傳了三種方法，我自己一開始是按照第二種思路來(lái)思考這道問(wèn)題的。
  第一種思路是最基礎(chǔ)的，也是復(fù)雜度最高的。每次將所有的元素向右移動(dòng)1位，然后循環(huán)K次。這樣做時(shí)間復(fù)雜度O(nk)即O(nn)，我提交到leetcode后，當(dāng)數(shù)組元素出現(xiàn)較多的測(cè)試case就超時(shí)了。
  這里可優(yōu)化一點(diǎn)，就是設(shè)置K=K%N，因?yàn)镵若遠(yuǎn)大于N時(shí)，移動(dòng)K次和移動(dòng)K-N次是沒(méi)有區(qū)別的，多折騰一個(gè)來(lái)回。所以取余數(shù)來(lái)計(jì)算。
  這條思路的代碼就不貼了，移1位的操作只要設(shè)置一個(gè)tmp變量保存最后一個(gè)值num[n-1]，每前一個(gè)值賦給后一個(gè)，最后把tmp賦給nums[0]就行。

• 第二種思路，以空間換時(shí)間。比如[1,2,3,4,5,6,7]向右移動(dòng)3步到[5,6,7,1,2,3,4]，可以看成[1,2,3,4]向右移動(dòng)了3位，然后[5,6,7]向左移動(dòng)了4位。這樣可以把[5,6,7]提前保存在tmp數(shù)組里，等[1,2,3,4]移動(dòng)完后，再將tmp從第一位開始賦值給nums。
  所以先tmp緩存n-k到n-1這k個(gè)值，再移動(dòng)0到n-k-1的值右移k位，最后tmp賦值到nums首位。這樣時(shí)間復(fù)雜度為O(n+k)即O(n)，空間復(fù)雜度為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數(shù)組的方法，據(jù)說(shuō)速度更快，我還沒(méi)來(lái)得及研究。待續(xù)。