[LeetCode] Product of Array Except Self
Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
解题思路：
这道题的题意为给定一个数组A，求数组B，其中B为A中除对应元素外所有其他数组元素的乘积。
要求不能用除法，而且时间复杂度为O(n)
解法1：倘若用除法，先求出A中所有元素的乘积，然后将积除以对应元素。注意讨论是否为0。且本题不许用除法。
解法2：B中的元素等于对应元素A中所有左边元素的乘积*A中所有右边元素的乘积。可以用两个数组left、right记录所有对应元素左边和右边的乘积，然后相乘即可。
class Solution {
public:
vector productExceptSelf(vector& nums) {
int len = nums.size();
vector left(len, 1); //当前元素左边的乘积
vector right(len, 1); //当前元素右边的乘积
vector result;
for(int i=1; i=0; i--){
right[i] = right[i+1]*nums[i+1];
}
for(int i=0; i
解法3：题意要求以空间复杂度为O（1）的方法来解决，上种解法的空间复杂度为O(n)。优化后的代码如下：
class Solution {
public:
vector productExceptSelf(vector& nums) {
int len = nums.size();
vector result(len, 1);
for(int i=1; i=0; i--){
right *= nums[i + 1];
result[i] = result[i] * right;
}
return result;
}
};
<!--
-->
原文作者：；如有侵权，请联系管理员删除。
