- 給定一個數(shù)組蛉威，將數(shù)組中的元素向右移動 k 個位置，其中 k 是非負數(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)上流傳了三種方法僻弹，我自己一開始是按照第二種思路來思考這道問題的。
第一種思路是最基礎(chǔ)的并炮，也是復(fù)雜度最高的默刚。每次將所有的元素向右移動1位，然后循環(huán)K次逃魄。這樣做時間復(fù)雜度O(nk)即O(nn)荤西，我提交到leetcode后，當(dāng)數(shù)組元素出現(xiàn)較多的測試case就超時了。
這里可優(yōu)化一點邪锌，就是設(shè)置K=K%N勉躺，因為K若遠大于N時，移動K次和移動K-N次是沒有區(qū)別的觅丰，多折騰一個來回饵溅。所以取余數(shù)來計算。
這條思路的代碼就不貼了舶胀，移1位的操作只要設(shè)置一個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數(shù)組里基茵，等[1,2,3,4]移動完后奋构，再將tmp從第一位開始賦值給nums。
所以先tmp緩存n-k到n-1這k個值拱层，再移動0到n-k-1的值右移k位弥臼，最后tmp賦值到nums首位。這樣時間復(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ù)說速度更快烙肺，我還沒來得及研究纳猪。待續(xù)。
