实现Python3数组旋转的3种算法实例
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的长度取余，就是最终我们需要移动的位置
代码如下：
if nums: 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)，取余
代码如下：
if nums:
k = k % len(nums)
while k > 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),取余操作，减少重复的次数。
代码如下：
if nums:
old_nums = nums[:]
l = len(nums)
for x in range(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种算法实例的文章就介绍到这了,更多相关3种算法实现Python3数组的旋转内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。