轮转数组(Python代码)

本文主要是介绍轮转数组(Python代码)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

力扣（leetcode）-初级算法

轮转数组-做题思路与解法解析

示例一：

​ 输入: 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]

示例二：

​ 输入：nums = [-1,-100,3,99], k = 2
​ 输出：[3,99,-1,-100]
​ 解释:
​ 向右轮转 1 步: [99,-1,-100,3]
​ 向右轮转 2 步: [3,99,-1,-100]

现在我们来看这道题。

思路一：两个循环嵌套，第一个是执行k次轮转，第二个是具体每一次轮转元素的改变

def main(nums,k):
    for i in range(k):
        temp=nums[-1]#将列表最后一个元素存在temp因为每一步都是将列表最后一个元素移到列表的第一位，其余的往右边移动一位
        for j in range(len(nums)-2,-1,-1):#从倒数第二个元素，到第0个元素，进行循环
            nums[j+1]=nums[j]#将每个元素向右移动一位
        nums[0]=temp#将列表最后一位元素移到第一位

时间复杂度O(k*n)

这样思路是正确的，但是由于时间复杂过大，所以在运行时超时了，呜呜呜呜......

思路二：用列表的切片来写，通过示例一，我们可以很明显的观察到，当k=3时，最后得到的列表的前三位时原来列表的后三位，后四位时原来列表的前四位。所以我们可以用列表的切片来写。

k %= len(nums)取余是方便当k大于列表的长度的计算
nums[:] = nums[-k:]+nums[:-k]#加一个列表的浅拷贝

时间复杂度O（n-k）(这个我也不太确定，列表切片的时间复杂度应该时O（K），k代表切片中元素的个数)

思路三：依旧是轮转，但是这次我们只用一个循环，因为列表元素每次都往右移动一位，当越界的时候就会变成第一位，取余操作可以很好的解决当越界时元素应该在的位置。

for i in range(len(nums)):
    lists.append(nums[i])#复制列表
for i in range(len(nums)):
    nums[(i+k)%len(nums)]=lists[i]#旋转列表

时间复杂度O(n)

空间复杂度O(n)

后续有新方法会更新

未完待续中.......

题目链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/

这篇关于轮转数组(Python代码)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！