283.除自身以外数组的乘积（前缀积、C解法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了283.除自身以外数组的乘积（前缀积、C解法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述：

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

前缀积解法：

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int* ans = (int *)malloc(sizeof(int) * numsSize);
    *returnSize=numsSize;

    ans[0]=1;
    for(int i=1;i<numsSize;i++){
        ans[i]=ans[i-1]*nums[i-1];
    }
    int r=1;
    for(int i=numsSize-1;i>=0;i--){
        ans[i]*=r;
        r*=nums[i];
    }
    return ans;
}

分析：

该思路和前缀和有点类似，即计算下一个元素的积时有很大一部分计算是与计算上一个元素的积重复的，用前缀积数组存储计算值，在该值的基础上进行下一个计算，减少了重复运算，达到降低时间复杂度的效果。

每一个元素除自身以外数组的积可以分解为前缀积乘以后缀积，后缀积求法与前缀积类似，只是遍历的顺序相反。可以用两个数组，两个for循环分别求前缀积、后缀积，再用一个数组，一个for循环计算题解，这种解法思路更直接，但开了三个数组空间复杂度高。本解法选择用一个for循环将题解数组当作前缀积数组，再用一个for循环同时计算后缀积和题解，这样只开了一个数组。

需注意，函数中定义的数组（int ans[returnSize];)是局部变量，离开函数后会自动释放，不能用return传出去，必须用malloc定义数组。文章来源地址https://www.toymoban.com/news/detail-817589.html

到了这里，关于283.除自身以外数组的乘积（前缀积、C解法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！