Python3实现旋转数组的3种算法

淡淡的烟草味﹌ 2022-03-08 11:50 117阅读 0赞

下面是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\]