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/