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].
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:    }  

No comments: