Python实现的旋转数组功能算法示例
本文实例讲述了Python实现的旋转数组功能算法。分享给大家供大家参考，具体如下：
一、题目
给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。
例1：
输入:[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]
例2：
输入:[-1,-100,3,99]和k=2
输出:[3,99,-1,-100]
解释:
向右旋转1步:[99,-1,-100,3]
向右旋转2步:[3,99,-1,-100]
说明：
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，击败了98%
附：本机测试示例代码：
#-*-coding:utf-8-*- nums=[1,2,3,4,5,6,7] k=3 ifnums: k=k%len(nums) nums[:]=nums[-k:]+nums[:-k] print(nums)
运行结果：
[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，击败了16%
附：本机测试示例代码：
#-*-coding:utf-8-*- nums=[1,2,3,4,5,6,7] k=3 ifnums: k=k%len(nums) whilek>0: k-=1 nums.insert(0,nums[-1]) nums.pop() print(nums)
运行结果：
[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，击败了98%
附：本机测试示例代码：
#-*-coding:utf-8-*- nums=[1,2,3,4,5,6,7] k=3 ifnums: old_nums=nums[:] l=len(nums) forxinrange(l): nums[(x+k)%l]=old_nums[x] print(nums)
运行结果：
[5,6,7,1,2,3,4]
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数组操作技巧总结》、《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。