【Leetcode】238. Product of Array Except Self

Description

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

Solution

public int[] productExceptSelf(int[] nums) {
        int result = 1;
        int[] tran = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result *= nums[i];
        }
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) {
                tran[j] = 1;
                for (int k = 0; k < nums.length/* && k != j && nums[k] != 0*/; k++) {
                    if (k == j) {
                        continue;
                    }
                    tran[j] *= nums[k];
                }
            } else {
                tran[j] = result / nums[j];
            }

        }
        return tran;

    }

Analyse

这里就是简单的运算然后判0，但是这个时间复杂度到了O(n ^ 2)，而且要注意的地方就是for循环里，一定不能把条件直接加进去，而是要在函数体里写判定然后continue跳出就可以。因为for里面的for如果在条件判断里加的话，若失败就直接跳到外层，而在里面用continue则可以保持外层的值不变，继续判断内层的下一个值。

Optimization

public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        res[0] = 1;
        for (int i = 1; i < len; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        //now res = {1, 1, 2, 6};
        //nums = {1, 2, 3 ,4};
        //res[3] = 6 * 1;
        //res[2] = 2 * 4;
        //res[1] = 1 * 3 * 4;
        //res[0] = 1 * 2 * 3 * 4;
        int right = 1;
        for (int j = len - 1; j >= 0; j--) {
            res[j] *= right;
            right *= nums[j];
        }
        return res;
    }

Analyse

这个就是把结果分边，先左后右，复杂度降低到了O(n)。