Loading... ### LeetCode 238: 除自身以外数组的乘积 #### 问题描述 给定一个整数数组 `nums`,返回一个数组 `answer`,其中 `answer[i]` 是 `nums` 中除 `nums[i]` 以外其余各元素的乘积。 你必须在 **O(n)** 时间复杂度内完成此操作,且不能使用除法运算。 **示例:** ``` 输入: nums = [1, 2, 3, 4] 输出: [24, 12, 8, 6] ``` #### 解决方案 本题要求我们在不使用除法的前提下,计算每个位置的元素除外的数组乘积,且要求时间复杂度为 O(n)。这需要我们用到巧妙的前缀和后缀乘积的思路。 基本思路是:通过两次遍历,第一次计算每个元素左边的乘积,第二次计算每个元素右边的乘积,最终将两者相乘得到结果。 #### 详细步骤 1. **初始化**: - 创建一个数组 `answer`,用来存放结果,长度与 `nums` 相同,初始值为 1。 - 创建两个变量 `left` 和 `right`,分别用于记录从左到右和从右到左的乘积。 2. **计算左侧乘积**: - 从左到右遍历 `nums`,将每个位置的左侧所有元素的乘积存入 `answer` 数组。 - `answer[i] = left`,然后更新 `left` 为 `left * nums[i]`。 3. **计算右侧乘积并更新最终结果**: - 从右到左遍历 `nums`,将每个位置的右侧所有元素的乘积乘以之前计算的左侧乘积。 - `answer[i] = answer[i] * right`,然后更新 `right` 为 `right * nums[i]`。 #### 代码实现 以下是基于上述思路的 Python 实现: ```python def productExceptSelf(nums): n = len(nums) answer = [1] * n # 计算左侧乘积 left = 1 for i in range(n): answer[i] = left left *= nums[i] # 计算右侧乘积并更新最终结果 right = 1 for i in range(n-1, -1, -1): answer[i] *= right right *= nums[i] return answer ``` #### 解释 - **左侧乘积计算**:我们用 `left` 来累计 `nums` 中每个元素左侧的乘积。在第一次遍历中,`left` 累计的是当前元素左边所有元素的乘积。 - **右侧乘积计算**:类似的,`right` 用来累计 `nums` 中每个元素右侧的乘积。在第二次遍历中,`right` 累计的是当前元素右边所有元素的乘积。 - **最终结果**:由于 `answer[i]` 初始存储的是左侧乘积,而后我们将其乘以右侧乘积,最终得到 `nums[i]` 之外所有元素的乘积。 #### 复杂度分析 - **时间复杂度**:O(n)。我们对数组进行了两次遍历,因此时间复杂度为线性。 - **空间复杂度**:O(1)(如果不考虑输出数组 `answer` 的空间)。我们仅用了常数级的额外空间来存储 `left` 和 `right` 的乘积,额外空间复杂度为常数级别。 ### 思维导图 ```mind LeetCode 238 - 除自身以外数组的乘积 1. 输入数组 nums 1.1 计算左侧乘积 1.2 计算右侧乘积 2. 结果数组 answer 2.1 存储每个元素的左侧乘积 2.2 更新右侧乘积并与左侧乘积相乘 3. 输出结果 answer ``` ### 总结 这道题通过左右两次遍历,巧妙地解决了如何在 O(n) 时间复杂度内计算每个元素除外的数组乘积问题,避免了直接使用除法。通过前缀乘积和后缀乘积的组合,我们实现了所需的结果,同时保持了高效的空间利用和时间复杂度。 最后修改:2024 年 08 月 23 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏