力扣经典数组算法：轮转数组与除自身外乘积详解

1. 项目概述

今天要分享的是力扣（LeetCode）打卡第8天的两道经典算法题解——"轮转数组"和"除自身外乘积"。这两道题分别来自数组操作类别的中等难度题目，在面试中出现的频率相当高。作为刷题路上的必经关卡，它们能很好地检验我们对数组基本操作的掌握程度，以及解决实际问题时的算法思维。

轮转数组（Rotate Array）要求我们在不额外开辟数组空间的情况下，将数组元素向右轮转k个位置。而除自身外乘积（Product of Array Except Self）则需要我们计算数组中每个元素除自身外所有其他元素的乘积，同样要求不能使用除法运算。这两道题看似简单，但都暗藏玄机，有多种解法思路，也涉及空间复杂度优化的技巧。

2. 轮转数组解法详解

2.1 问题描述与示例

给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。例如：

输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]

2.2 暴力解法与问题分析

最直观的解法可能是每次将数组元素向右移动一位，重复k次。这种方法的时间复杂度是O(n*k)，当k很大时效率极低。而且题目明确要求使用原地算法，即空间复杂度应为O(1)。

注意：在实际编码时，k可能大于数组长度n，这时实际有效轮转次数是k%n，因为轮转n次等于没有轮转。

2.3 三次反转法（最优解）

更高效的解法是使用三次反转法，这也是面试官最希望看到的解法：

  1. 反转整个数组
  2. 反转前k个元素
  3. 反转剩下的n-k个元素

以nums = [1,2,3,4,5,6,7], k=3为例：

  1. 整体反转：[7,6,5,4,3,2,1]
  2. 反转前3个：[5,6,7,4,3,2,1]
  3. 反转后4个：[5,6,7,1,2,3,4]
def rotate(nums, k): n = len(nums) k %= n def reverse(start, end): while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1 reverse(0, n-1) reverse(0, k-1) reverse(k, n-1)

2.4 环状替换法

另一种思路是环状替换：将每个元素直接放到它最终应该在的位置。这种方法需要处理多个环的情况，实现起来较为复杂，但同样是O(n)时间复杂度和O(1)空间复杂度。

3. 除自身外乘积解法详解

3.1 问题描述与示例

给你一个整数数组nums，返回数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。题目要求不能使用除法，且在O(n)时间复杂度内完成。

示例： 输入: nums = [1,2,3,4] 输出: [24,12,8,6]

3.2 左右乘积列表法

最直观的解法是计算每个元素左边所有元素的乘积和右边所有元素的乘积，然后将两者相乘。具体步骤：

  1. 初始化两个数组left和right，分别存储每个元素左边和右边的乘积
  2. left[i] = left[i-1] * nums[i-1]
  3. right[i] = right[i+1] * nums[i+1]
  4. answer[i] = left[i] * right[i]

这种方法的时间复杂度是O(n)，但空间复杂度也是O(n)，因为需要额外的left和right数组。

3.3 空间优化解法

我们可以优化空间复杂度到O(1)（不包括输出数组），方法是：

  1. 先用answer数组存储每个元素左边的乘积
  2. 然后从右向左遍历，用一个变量R记录右边的乘积，并更新answer数组
def productExceptSelf(nums): n = len(nums) answer = [1] * n # 计算左边乘积 for i in range(1, n): answer[i] = answer[i-1] * nums[i-1] # 计算右边乘积并合并结果 R = 1 for i in range(n-1, -1, -1): answer[i] = answer[i] * R R *= nums[i] return answer

3.4 边界情况处理

在实际编码时，需要注意以下边界情况：

  • 数组长度为1时，结果应为[1]
  • 数组中有0的情况（特别是多个0的情况）
  • 大数相乘可能导致溢出（虽然Python不用担心这个问题）

4. 常见问题与调试技巧

4.1 轮转数组常见错误

  1. 未处理k大于数组长度的情况：应该先计算k%n
  2. 反转边界错误：注意数组索引从0开始，最后一个元素是n-1
  3. 原地修改时顺序错误：三次反转的顺序不能错

调试技巧：

  • 打印中间结果验证每次反转后的数组状态
  • 使用小数组（如长度3-5）手动模拟过程

4.2 除自身外乘积常见错误

  1. 初始化answer数组时忘记第一个元素应为1
  2. 从右向左遍历时更新R的顺序错误（应先计算answer[i]再更新R）
  3. 处理0的情况时逻辑混乱

调试技巧：

  • 分别打印左边乘积和右边乘积的中间结果
  • 对于含0的数组，特别检查结果是否正确

5. 算法复杂度分析

5.1 轮转数组复杂度

  • 时间复杂度：O(n)，每个元素被访问固定次数
  • 空间复杂度：O(1)，原地修改，只用了常数额外空间

5.2 除自身外乘积复杂度

  • 时间复杂度：O(n)，两次线性遍历
  • 空间复杂度：O(1)（不包括输出数组），优化后只用了常数额外空间

6. 实际应用场景

这两道算法题虽然看起来是纯粹的编程练习，但它们在实际开发中有广泛的应用：

  1. 轮转数组：

    • 图像处理中的像素移位
    • 缓冲区循环利用
    • 密码学中的轮转加密

  2. 除自身外乘积：

    • 统计计算中的累积量
    • 信号处理中的滤波器设计
    • 金融分析中的收益率计算

7. 扩展思考与变种问题

7.1 轮转数组变种

  1. 向左轮转而非向右
  2. 轮转链表而非数组
  3. 轮转二维矩阵

7.2 除自身外乘积变种

  1. 允许使用除法时的解法
  2. 计算除当前元素外前k个元素的乘积
  3. 多维数组的类似操作

8. 个人刷题心得

在解决这两道题的过程中，我总结了几个重要的经验：

  1. 对于数组操作问题，画图是最有效的理解方式。手动模拟几次操作过程，规律就会显现。
  2. 空间复杂度优化往往需要巧妙的数学观察，比如三次反转法和乘积的前后分解。
  3. 边界条件测试非常重要，特别是数组长度为0或1，以及k为0或大于n的情况。
  4. 在面试中，即使知道暴力解法，也应该主动思考更优解，并解释优化思路。

刷题时我习惯先用暴力解法确保理解题意，然后再思考优化方案。对于这两道题，三次反转法和左右乘积分解都是非常巧妙的解法，值得牢记。在实际编码时，变量命名和注释也很重要，特别是处理多个指针或临时变量时。