力扣网C语言编程题：除自身以外数组的乘积

一. 简介

本文记录力扣网上涉及数组方面的编程题，主要以 C语言实现。

二. 力扣上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]

提示：

    2 <= nums.length <= 105
    -30 <= nums[i] <= 30
    输入 保证 数组 answer[i] 在  32 位 整数范围内

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

解题思路：

分析题目：分析题目的意思，第i个元素的值为其前面所有元素（即前缀元素）的乘积与 其后面的元素（即后缀元素）的乘积。

初步思路：

(1) 遍历数组，得到每个元素的所有前缀元素的乘积；

(2) 再遍历一遍数组，得到每个元素的所有后缀元素的乘积（从数组后往前计算）；

(3) 最后再遍历一次数组，将前面两次遍历获取的前缀元素的乘积与后缀元素的乘积进行乘积计算，即可得到每个元素的值。

C语言实现如下：

#include <stdio.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    if((nums == NULL) || (numsSize <= 0)) {
        return NULL;
    }

    int i = 0;
    int* prefix_ptr = (int*)malloc(numsSize * sizeof(int));
    int* suffix_ptr = (int*)malloc(numsSize * sizeof(int));
    int* ret_ptr = (int*)malloc(numsSize * sizeof(int));

    prefix_ptr[0] = 1;
    //计算第i个元素的所有前缀元素的乘积
    for(i = 1; i < numsSize; i++) {
        prefix_ptr[i] = prefix_ptr[i-1]* nums[i-1];
    }

    //计算第i个元素的所有后缀元素的乘积
    suffix_ptr[numsSize-1] = 1;
    for(i = 1; i < numsSize; i++) {
        suffix_ptr[numsSize-i-1] = suffix_ptr[numsSize-i] * nums[numsSize-i];
    }

    //将前面的前缀元素的乘积与 后缀元素的乘积进行乘积计算
    for(i = 0; i < numsSize; i++) {
        ret_ptr[i] = prefix_ptr[i] * suffix_ptr[i];
    } 

    *returnSize = numsSize;
    free(prefix_ptr);
    prefix_ptr = NULL;
    free(suffix_ptr);
    suffix_ptr = NULL;
    return ret_ptr;  
}

可以看出，实现方法的时间复杂度为 O(n)， 空间复杂度为 O(n)。满足基本要求。

进阶解题方法

上面基础解题方法中，因为我们开辟了三个内存空间，（由于题目说返回空间不算）那么空间复杂度是 O(n)。根据题目最后进阶要求，空间复杂度要控制在 O(1)。

接下来就要对上述代码进行优化了，降低空间复杂度，也就是说只能开辟返回的buf，其他开辟空间的操作要优化掉。

解题思路：

1. 将上面三个缓存改为使用一个缓存，也就是只申请返回数据的缓存；

2. 将上面三个步骤在一次遍历数组过程中完成；

具体实现方法：

1. 首先，申请一段numsSize大小的缓存，所有元素初始化为1（因为1与任何值的乘积都为任何值，不会产生任何影响）；

2. 遍历一次数组，求前缀元素乘积，后缀元素乘积，计算前缀元素乘积与后缀元素乘积的乘积，这三步同时完成；

计算第i个元素的 所有前缀元素的乘积，然后计算其所有后缀元素的乘积；将前缀乘积值计算乘积，再将后缀乘积值计算 乘积；

C语言实现如下：

#include <stdio.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    if((nums == NULL) || (numsSize <= 0)) {
        return NULL;
    }

    int i = 0;
    int * ret_ptr = (int*)malloc(numsSize * sizeof(int));
    //首先将数组元素初始化为 1
    for(i = 0; i < numsSize; i++) {
        ret_ptr[i] = 1;
    }

    int prefix = 1;
    int suffix = 1;
    for(i = 1; i < numsSize; i++) {
        //计算第i个元素的所有前缀元素的乘积
        prefix *= nums[i-1];
        //计算第i个元素的所有后缀元素的乘积
        //注意：计算后缀元素乘积时需要从后往前计算
        suffix *= nums[numsSize-i];
        //每一轮循环将元素的前缀元素乘积计算
        ret_ptr[i] *= prefix;
        //每一轮循环将元素的后缀元素乘积计算
        ret_ptr[numsSize-i-1] *= suffix;
    }

    *returnSize = numsSize;
    return ret_ptr;
}