Python3实现旋转数组的3种算法
推荐
在线提问>>
下面是Python3实现的旋转数组的3种算法。
一、题目
给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。
例如：
输入:[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]
说明：
1.尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
2.要求使用空间复杂度为O(1)的原地算法。
二、解题算法
解法一
以倒数第k个值为分界线，把nums截成两组再组合。因为k可能大于nums的长度(当这两者相等的时候，就相当于nums没有移动)，所以我们取k%len(nums)，k和nums的长度取余，就是最终我们需要移动的位置
代码如下：
ifnums:
k=k%len(nums)
nums[:]=nums[-k:]+nums[:-k]
时间：64ms
假设：
nums=[1,2,3,4,5,6,7]
k=3
运行结果：
[5,6,7,1,2,3,4]
解法二
先把nums最后一位移动到第一位，然后删除最后一位，循环k次。k=k%len(nums)，取余
代码如下：
ifnums:
k=k%len(nums)
whilek>0:
k-=1
nums.insert(0,nums[-1])
nums.pop()
时间：172ms
假设：
nums=[1,2,3,4,5,6,7]
k=3
运行结果：
[5,6,7,1,2,3,4]
解法三
先把nums复制到old_nums，然后nums中索引为x的元素移动k个位置后,当前索引为x+k，其值为old_nums[x]。，所以我们把x+k处理成(x+k)%len(nums),取余操作，减少重复的次数。
代码如下：
ifnums:
old_nums=nums[:]
l=len(nums)
forxinrange(l):
nums[(x+k)%l]=old_nums[x]
时间：64ms
假设：
nums=[1,2,3,4,5,6,7]
k=3
运行结果：
[5,6,7,1,2,3,4]
以上内容为大家介绍了Python3实现旋转数组的3种算法，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注IT培训机构:千锋教育。http://www.mobiletrain.org/
