一. 簡介

本文記錄力扣網上涉及數組方面的編程題，主要以 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));//首先將數組元素初始化為 1for(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;
}