Python3实现数组向右旋转的三种算法详解

Python3实现数组向右旋转的三种算法详解

Python3实现数组向右旋转的三种算法

以下展示在Python3环境下实现数组向右旋转功能的三种具体算法方案。

题目要求与示例

一、题目要求

给定一个整数数组，要求将数组中的元素整体向右移动 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 可能大于数组长度，当 k 与数组长度相等时数组实际未发生移动，因此需计算 k % len(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，随后遍历原数组。对于索引为 x 的元素，其移动后的新索引为 x+k。为避免越界，将新索引处理为 (x+k)%len(nums)，通过取余操作减少重复计算次数，并将 old_nums[x] 的值赋给新位置。

具体代码实现如下：

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实现数组旋转的三种算法实例介绍完毕。如需了解更多相关算法内容，可搜索本站历史文章或继续浏览后续相关文章，感谢大家的支持！