## Sunday, October 25, 2015

### [Leetcode] Product of Array Except Self, Solution

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]`.
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.)
[Thoughts]

`output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

output[i] =  { i 前面的数的乘积}  X  { i 后面的数的乘积}

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

github: https://github.com/codingtmd/leetcode/blob/master/src/Product%20of%20Array%20Except%20Self.cpp

1. 数组中有一个以上的0出现， 比如 [1,2, 0, 0, 3, 4]， 最后的结果肯定都是0： [0,0,0,0,0,0]
2. 数组中有一个0出现，比如[1,2,0,3,4]，按照题目的定义，最后的输出结果是[0,0,24,0,0]. 除了0的那一位是有值，其他位都是0
3. 数组中没有0， 假设数组位[a0, a1, a2, ......], 其中所有数值的乘积为M， 那个数组的输出就是[M/a0, M/a1, M/a2.....].

[Code]
``````1:    vector<int> productExceptSelf(vector<int>& nums) {
2:      int64_t product = 1;
3:
4:      int zeros = 0;
5:      for(int i =0; i< nums.size(); i++) {
6:        if(nums[i] == 0){
7:          zeros++;
8:          continue;
9:        }
10:        product *= nums[i];
11:      }
12:
13:      vector<int> result;
14:      for(int i =0; i< nums.size(); i++) {
15:        if(zeros > 1) {
16:          result.push_back(0);
17:          continue;
18:        } else if( zeros == 1){
19:          if(nums[i] == 0) result.push_back(product);
20:          else result.push_back(0);
21:          continue;
22:        }
23:
24:        result.push_back(product/nums[i]);
25:      }
26:
27:      return result;
28:    }
``````