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

不能用除法，那我们分两次进行，一次将第i位之前的乘起来得到a，再把之后的乘起来得到b，a*b即是我们需要的结果。

 1 class Solution {
 2 public:
 3     vector<int> productExceptSelf(vector<int>& nums) {
 4         int n = nums.size();
 5         vector<int> result(n,1);
 6         int product = 1;
 7         for(int i=1;i<n;i++)
 8         {
 9             product = product*nums[i-1];
10             result[i] = product;
11         }
12         product = 1;
13         for(int i=n-2;i>=0;i--)
14         {
15             product = product*nums[i+1];
16             result[i] = result[i]*product;
17         }
18         return result;
19     }
20 };

[LeetCode]Product of Array Except Self

原文：http://www.cnblogs.com/Sean-le/p/4788210.html