[LeetCode 238] Product of Array

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:

• Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Solution: 不能用除法的方法

1. 为什么不能用除法的方法。

   • 比如[0 ,1], 如果先把所有乘起来，再除以本身。那么结果是[0, 0]。错误。
   • 如果乘积的时候排除0，乘积为1，再除以本身。那么结果是[1, 1]。错误。
   • 所以这种方法无法满足所有case

2. 用类似water trapping的方法

   • 对每个元素，用2个数组，分别存其左边元素的积 和 其右边元素的积。
   • 结果就是，左边积 * 右边积。 但是空间复杂度不合符

3. 优化，其实可以只用一个array来存结果，先从左到右，求出每个元素左边的积和
   再从右到左，用一个变量存每个元素右边的积，再与当前result[i]相乘，来覆盖 result[i]

1. 未优化空间复杂度

 //  Solution 1: Space O(n)
// 对每个元素，用2个数组，分别存其左边元素的积 和 其右边元素的积。
// 结果就是，左边积 * 右边积。 但是空间复杂度不合符。
// 优化，其实可以只用一个array来存结果，先从左到右，求出每个元素左边的积和
// 再从右到左，有一个变量存每个元素右边的积，再与当前result[i]相乘，===》 replace result[i]
class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0)
            return nums;
        
       
        int[] productToLeft = new int[nums.length];
        int[] productToRight = new int[nums.length];
        
        //1. construct each num's left nums product
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                productToLeft[i] = 1;
                continue;
            }
               
            productToLeft[i] = productToLeft[i - 1] * nums[i - 1];
        }
        
        //2. construct each num's right nums product
        for (int i = nums.length - 1; i >= 0 ; i--) {
            if (i == nums.length - 1) {
                productToRight[i] = 1;
                continue;
            }
               
            
            productToRight[i] = productToRight[i + 1] * nums[i + 1];
        }
        
        for (int i = 0; i < nums.length; i++) {            
            productToLeft[i] = productToLeft[i] * productToRight[i];
        }
        
        return productToLeft;
    }
}

2. 优化空间复杂度

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0)
            return nums;
        
        int[] result = new int[nums.length];
        result[0] = 1;
        
        //1. left to right: construct toLeftProduct of each num
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        //2. right to left: construct toRightProduct of each num
        int prevProduct = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            prevProduct = prevProduct * nums[i + 1];
            result[i] = result[i] * prevProduct;
        }
        
        return result;
    }
}