题目描述

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

解题思路一：切片

第一步求出了k与nums长度的余数是为了避免出现k>len(nums)的情况出现, 然后在进行切片，把切下来的倒数k个元素放到列表最前面即可。值得注意的是，在python中以nums = nums[-k:]+…的形式不能顺利赋值，需要以全切的方式nums[:]才可以。

class Solution:
def rotate(self, nums: List[int], k: int) -> None:
    if k == 0: return
    k = k%len(nums)
    nums[:] = nums[-k:] + nums[:-k]

复杂度分析：

时间复杂度：O(N) 此算法时间都花在切片上，所以是O(N)

空间复杂度: O(N) 切片所开辟出来的空间为O(N)

解题思路二： 数组翻转

数组翻转也就是俗称的三次翻转

当我们将数组的元素向右移动k次后，尾部的n个元素会将移动到头部。那我们是否可以走这种思路：

1. 先翻转整个数组，将尾部的元素翻转到头部
2. 再翻转整个数组的前k个元素
3. 最后再翻转数组后n-k个元素

以n=7，k=3为例

操作	结果
原始数组	1 2 3 4 5 6 7
翻转整个数组	7 6 5 4 3 2 1
翻转前k个元素	5 6 7 4 3 2 1
翻转后n-k个元素	5 6 7 1 2 3 4

代码实现

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(nums, start, end):
            while start < end:
                tmp = nums[start]
                nums[start] = nums[end]
                nums[end] = tmp
                start += 1
                end -= 1
        
        k %= len(nums)
        reverse(nums, 0, len(nums)-1)
        reverse(nums, 0, k-1)
        reverse(nums, k, len(nums)-1)

复杂度分析

时间复杂度 O(N) 进行了三次翻转，每个元素被翻转了两次，操作次数为2n = O(N)

空间复杂度 O(1) 空间上只用了tmp整个临时变量，复杂度为常数复杂度O(1)