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]

