题目
给你一个整数数组 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 <= 10^5
- -30 <= nums[i] <= 30
- 保证数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
代码
完整代码
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
int* result = (int*)calloc(numsSize, sizeof(int));
int* leftMult = (int*)calloc(numsSize, sizeof(int));
int* rightMult = (int*)calloc(numsSize, sizeof(int));
*returnSize = numsSize;
leftMult[0] = 1;
rightMult[numsSize-1] = 1;
for (int i = 1; i < numsSize; i++)
{
leftMult[i] = leftMult[i-1] * nums[i-1];
rightMult[numsSize - 1 - i] = rightMult[numsSize - i] * nums[numsSize - i];
}
for (int i = 0; i < numsSize; i++)
{
result[i] = leftMult[i]*rightMult[i];
}
free(leftMult);
free(rightMult);
return result;
}
思路分析
这套代码用了前缀积和后缀积的方法。
- 初始化两个数组
leftMult和rightMult，分别存储从左到右的前缀积和从右到左的后缀积。 - 第一次遍历计算
leftMult数组和rightMult数组。 - 最后一次遍历结合
leftMult和rightMult的值计算出结果result。
拆解分析
- 初始化及内存分配
int* result = (int*)calloc(numsSize, sizeof(int));
int* leftMult = (int*)calloc(numsSize, sizeof(int));
int* rightMult = (int*)calloc(numsSize, sizeof(int));
*returnSize = numsSize;
leftMult[0] = 1;
rightMult[numsSize-1] = 1;
分配结果数组和前缀、后缀数组的内存，并初始化第一个前缀和最后一个后缀的值为1。
- 计算前缀积数组
for (int i = 1; i < numsSize; i++)
{
leftMult[i] = leftMult[i-1] * nums[i-1];
}
从左到右遍历数组，计算每个位置的前缀积。
- 计算后缀积数组
for (int i = 1; i < numsSize; i++)
{
rightMult[numsSize - 1 - i] = rightMult[numsSize - i] * nums[numsSize - i];
}
从右到左遍历数组，计算每个位置的后缀积。
- 计算结果数组
for (int i = 0; i < numsSize; i++)
{
result[i] = leftMult[i]*rightMult[i];
}
结合前缀积和后缀积，计算每个位置的结果。
- 释放内存
free(leftMult);
free(rightMult);
释放不再需要的内存。
复杂度分析
- 时间复杂度：O(n)，因为有两个独立的遍历操作，每次操作的时间复杂度都是 O(n)。
- 空间复杂度：O(n)，因为使用了两个额外的数组
leftMult和rightMult。
一题多解
单数组解法
完整代码
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
int* result = (int*)calloc(numsSize, sizeof(int));
*returnSize = numsSize;
result[0] = 1;
for (int i = 1; i < numsSize; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
int rightMult = 1;
for (int i = numsSize - 1; i >= 0; i--) {
result[i] = result[i] * rightMult;
rightMult *= nums[i];
}
return result;
}
思路分析
这套代码用了前缀积和后缀积的优化方法。
- 第一次遍历时计算前缀积并存储在结果数组
result中。 - 第二次遍历时从右到左计算后缀积，并直接更新结果数组
result。
拆解分析
- 初始化及内存分配
int* result = (int*)calloc(numsSize, sizeof(int));
*returnSize = numsSize;
result[0] = 1;
分配结果数组的内存，并初始化第一个前缀值为1。
- 计算前缀积
for (int i = 1; i < numsSize; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
从左到右遍历数组，计算每个位置的前缀积并存储在结果数组中。
- 计算后缀积并更新结果数组
int rightMult = 1;
for (int i = numsSize - 1; i >= 0; i--) {
result[i] = result[i] * rightMult;
rightMult *= nums[i];
}
从右到左遍历数组，计算每个位置的后缀积，并直接更新结果数组。
复杂度分析
- 时间复杂度：O(n)，因为有两个独立的遍历操作，每次操作的时间复杂度都是 O(n)。
- 空间复杂度：O(1)，因为只使用了一个额外的变量
rightMult，而输出数组不计入空间复杂度。
结果
前后缀分别申请：
复用result数组：
