LeetCode 238. 除自身以外数组的乘积

ShaccoKL / 2024-10-12 / 原文

给你一个整数数组 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 <= 105
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

思路

审题：

数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。可以用int保存所有乘积
不要使用除法 考虑到可能存在0

目标：ans[i] 是第i个元素前后两边元素乘积

难点：如何减少运算次数，考虑ans[i]和ans[i-1]，存在大量重复计算

解决：由前缀和思想，可将计算结果保存，减少重复计算

实现：

开两个数组分别计算前缀后缀乘积

时间复杂度O(n) 空间复杂度O(n)

 vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        vector<int> l = vector<int>(size,1);//前缀乘积
        vector<int> r = vector<int>(size,1);//后缀乘积
        vector<int> ans = vector<int>(size,1);
        //计算前缀积
        for(int i=1;i<size;i++) {
            l[i]=l[i-1]*nums[i-1];
        }
        //计算后缀积
        for(int i=size-2;i>=0;i--) {
            r[i]=r[i+1]*nums[i+1];
        }
     	//计算ans
        for(int i=0;i<size;i++) {
            ans[i]=l[i]*r[i];
        }
        return ans;
}

优化：利用ans数组保存计算中间值

vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        vector<int> ans = vector<int>(size,1);
        //计算前缀积
        for(int i=1;i<size;i++) {
            ans[i]=nums[i-1]*ans[i-1];
        }
        //ans[i]为0到i-1乘积  mul为i+1到nums[size-1]乘积 注意边界 从倒数第二个开始
        int mul = 1;
        for(int i = size-2;i>=0;i--) {
            mul*=nums[i+1];
            ans[i]*=mul;
        }
        return ans;
}

总结

重复计算——>前缀和——>保存计算中间值

进一步优化——>”原地保存”