10、轮转数组

题目描述

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [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]
链接：https://leetcode-cn.com/problems/rotate-array

方法1、三次反转

思路：

运行时间：52ms

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        三次反转
        """
        n = len(nums)
        k = k%n
        def swap(l,r):
            while(l<r):
                nums[l], nums[r] = nums[r], nums[l]
                l+=1
                r-=1
        
        swap(0,n-k-1)
        swap(n-k,n-1)
        swap(0,n-1)

2、用list的pop函数

思路：pop掉最后一个数，再把该数insert到第一位。

运行时间：1860ms（很慢很慢）

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        将最后一个数pop并插到第一位
        """
        n = len(nums)
        k%=n
        for _ in range(k):
            nums.insert(0, nums.pop())

3、创建临时数据存放

运行时间：40ms

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        用临时数组new存放
        """
        new = nums.copy()  # 不能直接赋值，会让nums和n一起变化 或直接 new=nums[:]
        l = len(nums)
        for i in range(l):
            k1 = (i+k)%l
            new[k1] = nums[i]
        for i in range(l):
            nums[i] = new[i]          

4、拼接前后数组

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        拼接前后数组
        """
        n = len(nums)
        k%=n
        nums[:] = nums[n-k:]+nums[:n-k]