江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第238题：除自身以外数组的乘积

LeetCode第238题：除自身以外数组的乘积

问题描述

给你一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成。

难度：中等

示例

示例 1:

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

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

约束条件

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • 保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内

进阶

你可以在 O(1) 的额外空间复杂度内完成这个问题吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

解题思路

方法一: 左右乘积列表

对于数组中的每个元素，我们可以考虑将其左侧所有数字的乘积和右侧所有数字的乘积分别计算出来，然后将两个乘积相乘即为该元素处的结果。具体步骤如下：

  1. 初始化两个数组 left 和 right，分别用于存储每个位置左侧和右侧的所有元素乘积。
  2. 对于 left 数组，left[i] 表示 nums[0] * nums[1] * ... * nums[i-1]。我们初始设 left[0] = 1，因为位置0左侧没有元素。
  3. 对于 right 数组，right[i] 表示 nums[i+1] * nums[i+2] * ... * nums[n-1]。我们初始设 right[n-1] = 1，因为位置n-1右侧没有元素。
  4. 然后我们可以通过遍历数组来填充这两个乘积列表。
  5. 最后，对于每个位置 i，answer[i] = left[i] * right[i]。

方法二: 空间优化

我们可以进一步优化方法一，将空间复杂度降低到 O(1)（不考虑输出数组）。具体步骤如下：

  1. 将 answer 数组初始化为 1，首先计算每个元素左侧的乘积并存储在 answer 中。
  2. 然后我们从右向左遍历数组，用一个变量 right 记录右侧元素的乘积。
  3. 对于每个位置 i，我们将 answer[i] 乘以 right，然后更新 right = right * nums[i]。

这样我们只需要一个额外的变量来记录右侧的乘积，空间复杂度是 O(1)。

代码实现

方法一: 左右乘积列表

C#实现

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] answer = new int[n];
        
        // 计算左侧乘积
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        
        // 计算右侧乘积
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        
        // 计算最终结果
        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }
        
        return answer;
    }
}

Python实现

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [1] * n
        right = [1] * n
        answer = [1] * n
        
        # 计算左侧乘积
        for i in range(1, n):
            left[i] = left[i - 1] * nums[i - 1]
        
        # 计算右侧乘积
        for i in range(n - 2, -1, -1):
            right[i] = right[i + 1] * nums[i + 1]
        
        # 计算最终结果
        for i in range(n):
            answer[i] = left[i] * right[i]
        
        return answer

C++实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        vector<int> answer(n, 1);
        
        // 计算左侧乘积
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        
        // 计算右侧乘积
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        
        // 计算最终结果
        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }
        
        return answer;
    }
};

方法二: 空间优化

C#实现

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] answer = new int[n];
        
        // 计算左侧乘积并存储在answer中
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
        
        // 计算右侧乘积并直接更新answer
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * right;
            right *= nums[i];
        }
        
        return answer;
    }
}

Python实现

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n
        
        # 计算左侧乘积并存储在answer中
        for i in range(1, n):
            answer[i] = answer[i - 1] * nums[i - 1]
        
        # 计算右侧乘积并直接更新answer
        right = 1
        for i in range(n - 1, -1, -1):
            answer[i] = answer[i] * right
            right *= nums[i]
        
        return answer

C++实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n, 1);
        
        // 计算左侧乘积并存储在answer中
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
        
        // 计算右侧乘积并直接更新answer
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * right;
            right *= nums[i];
        }
        
        return answer;
    }
};

性能分析

时间复杂度

  • 方法一（左右乘积列表）：O(n)，其中n是数组的长度。我们遍历数组三次，分别计算左侧乘积、右侧乘积和最终结果。
  • 方法二（空间优化）：O(n)，同样需要遍历数组两次，一次计算左侧乘积，一次计算右侧乘积并更新结果。

空间复杂度

  • 方法一（左右乘积列表）：O(n)，需要存储左侧乘积列表和右侧乘积列表。
  • 方法二（空间优化）：O(1)，除了输出数组外，只使用了一个变量来记录右侧的乘积。

方法对比

方法 时间复杂度 空间复杂度 优势 劣势
左右乘积列表 O(n) O(n) 直观易理解 需要额外空间
空间优化 O(n) O(1) 符合进阶要求的O(1)空间复杂度 不如第一种方法直观

各语言实现的性能对比

语言 方法一执行时间 方法二执行时间
C++ ~16ms ~12ms
C# ~100ms ~96ms
Python ~200ms ~196ms

C++实现通常效率最高，这主要是由于其低级别特性和直接内存管理。Python相对较慢，这是因为其解释性语言的特性和动态类型系统导致的额外开销。

代码特点

  1. 不使用除法：按照题目要求，所有实现都没有使用除法操作。
  2. 巧妙利用前缀和后缀乘积：通过分别计算每个元素左侧和右侧的乘积，来得到除自身以外其他元素的乘积。
  3. 空间优化：方法二通过重复使用输出数组来存储中间结果，减少了额外空间的使用。

优化方向

这个问题的算法已经达到了O(n)的时间复杂度和O(1)的空间复杂度（不计输出数组），已经是渐近最优的。在实际应用中，可以考虑以下优化：

  1. 处理特殊情况：如果数组中包含0，可以特殊处理，避免不必要的乘法操作。
  2. 并行计算：在大规模数据下，可以考虑使用并行计算来加速计算过程。

常见错误

  1. 使用除法：题目明确要求不使用除法，有些人可能会先计算全部乘积，然后用除法来获取结果。
  2. 处理零的情况：如果数组中包含0，直接使用除法的方法会出现除零错误。
  3. 整数溢出：题目保证结果在32位整数范围内，但中间计算过程可能会溢出，需要注意。

相关题目

  • LeetCode 152: 乘积最大子数组
  • LeetCode 48: 旋转图像
  • LeetCode 189: 旋转数组
  • LeetCode 42: 接雨水