LeetCode 238 - Product of Array Except Self

LeetCode – Product of Array Except Self (Java)

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

    public int[] productExceptSelf(int[] nums) {
        int sum = 1;
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i ++) {
            ans[i] = sum;
            sum *= nums[i];
        }
        sum = 1;
        for (int i = nums.length - 1;i >= 0; i --) {
            ans[i] *= sum;
            sum *= nums[i];
        }
        return ans;
    }

Solve it without division and in O(n).
http://shibaili.blogspot.com/2015/08/day-119-239-sliding-window-maximum.html

    vector<int> productExceptSelf(vector<int>& nums) {

        vector<int> left(nums.size(),1);

        vector<int> right(nums.size(),1);

        vector<int> rt(nums.size());

        for (int i = 1; i < nums.size(); i++) {

            left[i] = nums[i - 1] * left[i - 1];

        }

        for (int i = nums.size() - 2; i >= 0; i--) {

            right[i] = nums[i + 1] * right[i + 1];

        }

         

        for (int i = 0; i < nums.size(); i++) {

            rt[i] = left[i] * right[i];

        }

         

        return rt;

    }

X.
https://discuss.leetcode.com/topic/18864/simple-java-solution-in-o-n-without-extra-space

https://discuss.leetcode.com/topic/19033/my-simple-java-solution/3

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }
    return res;
}

constant space, output array doesn't count as extra space

    vector<int> productExceptSelf(vector<int>& nums) {

        vector<int> left(nums.size(),1);

        for (int i = 1; i < nums.size(); i++) {

            left[i] = nums[i - 1] * left[i - 1];

        }

         

        int right = 1;

        for (int i = nums.size() - 1; i >= 0; i--) {

            left[i] = right * left[i];

            right *= nums[i];

        }

         

        return left;

    }

http://www.programcreek.com/2014/07/leetcode-product-of-array-except-self-java/

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

http://algorithmsforever.blogspot.com/2011/10/product-array.html

1. Calculate backward product in product array P[i] = Product(A[i+1]*...*A[N])
2. Take a variable p=1
3. For each element of input, multiply it by p and multiply P[i] by p

void product_array(int[] input, int[] product, int N){

product[N-1] = 1;

for(int i=N-1; i>-1; i++){

product[i] = product[i+1]*input[i+1];

}

int p = 1;
for(int i=0; i<N; i++){

if(i > 0){

p *= input[i-1];

}

product[i] *= p;

}

}

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/238_Product_of_Array_Except_Self.java

    public int[] productExceptSelf(int[] nums) {
        int sum = 1, count = 0;
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] == 0) count ++;
            else sum *= nums[i];
        }
        for (int i = 0; i < nums.length; i ++) {
            nums[i] = nums[i] == 0 ?
                (count > 1 ? 0 : sum) :
                (count > 0 ? 0 : sum / nums[i]);
        }
        return nums;
    }

    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        Arrays.fill(ans, 1);
        int mul = 1;
        for (int i = 0; i < nums.length - 1; i ++) {
            mul *= nums[i];
            ans[i + 1] *= mul;
        }
        mul = 1;
        for (int i = nums.length - 1; i > 0; i --) {
            mul *= nums[i];
            ans[i - 1] *= mul;
        }
        return ans;
    }

要求⽤用除法写，处理理有零的各种情况

注意overflow，注意0