题目：

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.)

 

解释：

给定数组nums，返回一个数组，该数组的output[i]等于nums数组中除去nums[i]外所有元素的乘积。

要求：

1.不许使用除法。

2.时间复杂度为O(n)。

3.空间复杂度为O(1)。

 

分析：

思路1：使用变量product保存数组中所有元素的乘积，output数组中每一项即为product/当前数组元素。但由于题目中要求不可使用除法，因此该思路不可用。

思路2：使用两个数组left和right分别保存nums数组中对应元素左边元素的乘积和右边元素的乘积，则output数组中的每一项为left数组和right数组对应相乘。但此做法的空间复杂度不为O(1)。

思路3：对思路2进行简化。由于题目中说明输出数组不作为额外的空间计入空间复杂度，因此采用output数组代替left或right数组。使用变量right或left代替当前元素右边所有元素的乘积或左边所有元素的乘积。

 

代码：

1 class Solution { 2 public: 3 vector<int> productExceptSelf(vector<int>& nums) { 4 int i; 5 int len = nums.size(); 6 int right = 1; 7 vector<int> result(len, 1); 8 //计算每一项元素左边所有元素的乘积 9 for (i = 1; i < len; i++) { 10 result[i] = result[i - 1] * nums[i - 1]; 11 } 12 for (i = len - 2; i >= 0; i--) { 13 //计算每一项元素右边所有元素的乘积 14 right *= nums[i + 1]; 15 //与左边元素乘积相乘 16 result[i] *= right; 17 } 18 return result; 19 } 20 };

 

参考：

http://blog.csdn.net/sunao2002002/article/details/47089053#

 

转载于:https://www.cnblogs.com/sindy/p/6535520.html