238 Product of Array Except Self

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

Show Company Tags Show Tags Show Similar Problems

分析

输入：至少含有2个元素的数组nums

输出：同size的数组，元素为其余乘积

要求：计算复杂度：O(n)-----》暗示数组只能遍历一遍

Corner Case:

1.全是0

思路1：Brute Force

复杂度：O(n^2)

如何才能降低计算复杂度？-------》trade space for speed

思路2：多建两个数组

pFromBegin[i] = nums[0]num[1]...*num[i]

pFromEnd[i] = num[n-1]...num[i+1]*num[i]

output[i] = pFromBegin[i-1] * pFromEnd[i+1]

思路2实现遇到的问题

1.求数组的起点

由于pFromBegin[i] = pFromBegin[i-1] * nums[i];因此当i==0时需要特殊处理。

同理，由于pFromEnd[i] = pFromEnd[i+1] * nums[i];因此当i==pFromEnd.length-1时需要特殊处理。

还同理，由于output[i] = pFromBegin[i-1] * pFromEnd[i+1];因此当i==0或i==lengthOfNums-1时需要特殊处理。

2.关于求pFromEnd[i]，由于用到的是pFromEnd[i+1] ，因此for中的循环是递减

    for(int i=pFromEnd.length-1; i>= 0; i--)

思路2复杂度

1.算pFromBegin和pFromEnd-----》O(n)+O(n) 2.算output-----》O(n)

运算复杂度：O(n)

需要两个于输入数组尺寸相同的array，因此空间复杂度：O(n)

AC Code

public class Solution {
    public int[] productExceptSelf(int[] nums) {

    int lengthOfNums = nums.length;
    int[] output = new int[lengthOfNums];

    int[] pFromBegin = new int[lengthOfNums];
    int[] pFromEnd = new int[lengthOfNums];

    for(int i=0; i<pFromBegin.length; i++) {
        if(i==0) pFromBegin[i] = nums[i];
        else {
        pFromBegin[i] = pFromBegin[i-1] * nums[i];
        }
    }

    for(int i=pFromEnd.length-1; i>= 0; i--) {
        if(i==pFromEnd.length-1) pFromEnd[i] = nums[i];
        else {
        pFromEnd[i] = pFromEnd[i+1] * nums[i];
        }
    }

    for(int i=0; i<lengthOfNums; i++) {
        if(i==0) output[i] = pFromEnd[i+1];
        else if(i==lengthOfNums-1) output[i] = pFromBegin[i-1];
        else output[i] = pFromBegin[i-1] * pFromEnd[i+1];
    }

    return output;
    }
}

Follow Up:空间复杂度O(1)

其实不需要建立额外数组，可以直接在output中更新乘积