除自身以外数组的乘积

给你一个整数数组 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]

这题采用前后缀分解的方法。
$answer[i]$ 等于 $nums$ 中除了 $nums[i]$ 之外其余各元素的乘积。换句话说，如果知道了 $i$ 左边所有数的乘积，以及 $i$ 右边所有数的乘积，就可以算出 answer $[i]$。

于是：

• 定义 $pre[i]$ 表示从 $nums[0]$ 到 $nums[i−1]$ 的乘积。
• 定义 $suf[i]$ 表示从 $nums[i+1]$ 到 $nums[n−1]$ 的乘积。
• 那么 $answer[i]=pre[i]∗suf[i]$。

class Solution {
public:
  vector<int> productExceptSelf(vector<int>& nums) {
    int n=nums.size();
    vector<int> res(n,0);
        //vector<int> pre(n,1);
    vector<int> end(n,1);
    // for(int i=1;i<n;i++){
    //     pre[i]=pre[i-1]*nums[i-1];
    // }
    for(int i=n-2;i>=0;i--){
      end[i]=end[i+1]*nums[i+1];
    }
    int pre=1;
    for(int i=0;i<n;i++){
      res[i]=pre*end[i];
      pre*=nums[i];
    }
    return res;
  }
};

代码中的注释部分是计算前缀的方法。实际优化了一下，比原来少遍历一次数组。

更新日志

2024/12/13 13:22

查看所有更新日志

• 24fac-prepare interview于 2024/12/13