題目

難度：★☆☆☆☆
類型：數組

給定一個數組，將數組中的元素向右移動 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]

示例 2:

輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋:
向右旋轉 1 步: [99,-1,-100,3]
向右旋轉 2 步: [3,99,-1,-100]

說明:

盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題。
要求使用空間復雜度為 O(1) 的原地算法。

解答

方案1：一步一步旋轉

我們定義了一個函數rotate_1_step()，實現旋轉一步的功能，然后使用循環(huán)執(zhí)行多次列表旋轉，這種方法在列表中元素數量較少時行之有效，但是元素數量很大時會很慢。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        def rotate_1_step(nums):
            """
            實現旋轉一步的功能
            :param nums:
            :return:
            """
            tmp = nums[-1]
            for i in range(len(nums)-1, 0, -1):
                nums[i] = nums[i-1]
            nums[0] = tmp

        for _ in range(k):
            rotate_1_step(nums)

力扣提交果然超時。

方案2：列表連接

這個方法十分簡單，直接用將列表的兩個部分進行間接即可，但是空間復雜度較大。這里需要注意k的取值可能大于列表長度，需要進行取余處理。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        k = k%len(nums)        # 有必要計算一下如果旋轉步長超過一圈的情況
        nums[:] = nums[-k:]+nums[:-k]

方案3：使用隊列

把列表看成隊列，每一步旋轉可以看做彈出列表最后一個元素并加入到列表首端，同樣的操作執(zhí)行k次。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for _ in range(k):
            nums.insert(0, nums.pop())

方案4：雙重逆序

將整個列表逆序，并將列表兩部分內容再次通過逆序方式返回原順序。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        nums[:] = reversed(nums)
        nums[:k] = reversed(nums[:k])
        nums[k:] = reversed(nums[k:])

如有疑問或建議，歡迎評論區(qū)留言~