238. Product of Array Except Self (M)

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

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

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105

• -30 <= nums[i] <= 30

• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Solution:

https://www.jiuzhang.com/problem/product-of-array-except-self/ Version 1:

如果暴力计算每个位置的答案值的话，时间会达到O(N^2)。

如果先将所有数乘起来，每个位置除以当前的数，有可能会整型溢出。

观察可以发现，每个数其实就是它前面部分的积乘以后面部分的积。所有前缀的积，通过一次遍历即可算出来，后缀也是一样。我们可以边乘边算前缀积，同时将他乘在结果数组上，这样达到了O(1)的额外空间，同时不用到除法。

代码思路

1. 令result为一个全是1的数组。

2. 令前缀积prefixProduct等于1，后缀积postfixProduct等于1。

3. 正序遍历数组nums，第i个位置先将结果乘上prefixProduct，再将prefixProduct乘上nums[i]。

4. 逆序遍历数组nums，第i个位置先将结果乘上postfixProduct，再将postfixProduct乘上nums[i]。

5. 返回result。

复杂度分析

设数组长度为N。

时间复杂度

• 遍历两次数组，时间复杂度为O(N)。

空间复杂度

• 只需额外O(1)的时间，记录前缀积和后缀积。

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: the product of all the elements of nums except nums[i].
     */
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        int prefixProduct = 1, postfixProduct = 1;
        
        for (int i = 0; i < result.length; i++) {
            result[i] = 1;
        }
        
        // 将第 i 个位置乘上前 i - 1 个数的积
        for (int i = 0; i < result.length; i++) {
            result[i] *= prefixProduct;
            prefixProduct *= nums[i];
        }
        
        // 将第 i 个位置乘上后面数的积
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] *= postfixProduct;
            postfixProduct *= nums[i];
        }
        
        return result;
    }
}

Version 2:

Version 1 的空间复杂版。prefixProduct postfixProduct都用数组来装。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        int n = nums.length;
        
        int[] prefixProduct = new int[n];
        prefixProduct[0] = nums[0];
        for(int i = 1; i< n; i++ )
        {
            prefixProduct[i] = prefixProduct[i-1] * nums[i];
        }
        
        int[] postfixProduct = new int[n];
        postfixProduct[n-1] = nums[n-1];
        for(int i = n-2; i >= 0; i-- )
        {
            postfixProduct[i] = postfixProduct[i+1] * nums[i];
        }
        
        int[] result = new int[n];
        result[0] = postfixProduct[1];
        result[n-1] = prefixProduct[n-2];
        for(int i = 1; i< n-1; i++)
        {
            result[i] = prefixProduct[i-1] * postfixProduct[i+1];
        }
        
        return result;
        
    }
}