leetcode刷题日记——除自身以外数组的乘积

[ 题目描述 ]：

[ 思路 ]：

• 题目要求获取数组中每个元素除自己以外的各元素的乘积
• 最简单的方法就是算出数组所有元素的乘积，然后除以自身，即可得到除自身外各元素的乘积
  • 但要考虑到其自身为0的情况，即当期自身为0时，需要重新计算其他各元素乘积

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int mul=1;int* ans = malloc(numsSize * sizeof(int));for(int i=0;i<numsSize;i++){mul*=nums[i];ans[i]=1;}for(int i=0;i<numsSize;i++){if(nums[i]!=0){ans[i]*=mul/nums[i];}else{for(int j=0;j<numsSize;j++){if(j==i) continue;ans[i]*=nums[j];}}}*returnSize = numsSize;return ans;
}

• 但题目中要求不使用除法，且在O(n)时间复杂度内完成
  • 不使用除法，即计算当前元素左右两边所有元素的乘积，可以采用双指针向两边遍历求积
  • 时间复杂度为O(n²)，超出了时间限制

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int mul=1;int left=0,right=0;int *ans=(int*)malloc(sizeof(int)*numsSize);for(int i=0;i<numsSize;i++){left=i-1;right=i+1;ans[i]=1;while(left>=0){mul*=nums[left--];}while(right<numsSize){mul*=nums[right++];}ans[i]=mul;mul=1;}*returnSize=numsSize;return ans;
}

• 如果要在O(n)的时间复杂度内，就需要将左右乘积拿到for循环外面来做，但这样就只能做一次，得不到所有元素的左右乘积。
• 也就是说如果需要在O(n)的时间复杂度之内，完成，我们得先知道左右两边的乘积，即提前计算并存储
• 运行如下

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int mul=1;int *left=(int*)malloc(sizeof(int)*numsSize);int *right=(int*)malloc(sizeof(int)*numsSize);int *ans=(int*)malloc(sizeof(int)*numsSize);left[0]=1;right[numsSize-1]=1;for(int i=1;i<numsSize;i++){left[i]=left[i-1]*nums[i-1];right[numsSize-1-i]=right[numsSize-i]*nums[numsSize-i];}for(int i=0;i<numsSize;i++){ans[i]=left[i]*right[i];}*returnSize=numsSize;return ans;
}

• 时间复杂度为O(n)，空间复杂度为O(n)

[ 优化 ]：

• 题目进阶说可以仅使用O(1)的额外空间复杂度完成，但输出数组不算
• 也就是说用于记录的left,right,ans三个数组，仅有ans可以用
• 如果直接用ans存储left或者right中的其中一个，另一个又该如何存储
• 由于空间复杂度为O(1)，那就只能是常量right或者表达式right
• 运行如下

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int mul=1;int *ans=(int*)malloc(sizeof(int)*numsSize);ans[0]=1;int right=nums[numsSize-1];for(int i=1;i<numsSize;i++){ans[i]=ans[i-1]*nums[i-1]; }for(int i=numsSize-2;i>=0;i--){ans[i]*=right;right*=nums[i];}*returnSize=numsSize;return ans;
}

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

[ 官方题解 ]：

• 一、使用额外空间存储，左右两边乘积，上述第三段代码
• 二、不使用额外空间，对方法一的优化，上述第四段代码