題目

難度：★☆☆☆☆
類型：數(shù)組

給定一個(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]

示例 2:

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

說明:

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

解答

方案1：一步一步旋轉(zhuǎn)

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

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):
            """
            實(shí)現(xiàn)旋轉(zhuǎn)一步的功能
            :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)

力扣提交果然超時(shí)。

方案2：列表連接

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

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)        # 有必要計(jì)算一下如果旋轉(zhuǎn)步長超過一圈的情況
        nums[:] = nums[-k:]+nums[:-k]

方案3：使用隊(duì)列

把列表看成隊(duì)列，每一步旋轉(zhuǎn)可以看做彈出列表最后一個(gè)元素并加入到列表首端，同樣的操作執(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：雙重逆序

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

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ū)留言~