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

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

[Thoughts]

一般这种题都可以分解成若干子问题来解决。As defined, 

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

简单的说

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

问题就解决了，首先从前往后扫描数组一遍，对每一个i，得到{i 前面的数的乘积}(可以称做output_before)，然后在从后往前扫描数组一遍，获得 { i 后面的数的乘积}(可以称做output_after)。 将两数相乘即为所求。

举个例子(如下图)，nums = {1,2,3,4}, 第一遍，从前往后扫描一遍，得到的output_before = {1, 1, 2, 6}. 从后往前扫描一遍，得到的output_after = {24, 12, 4, 1}.

那么  output [i] = output_before[i] * output_after[i],   output = {24, 12, 8, 6}

[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:    }