238. Product of Array Except Self

思路

/*
        The given conditions restrict serveral approach to the problem. First one disables us to calculate a product of all the numbers and divide it by each number itself. The second one disables us to have a brute force solution to solve the problem.
        Here is the O(n) solution:
        For each of the number, calculate its left and right product. Store them in left product array and right product array array respectively.
        Finally for each of the number i, multiply left[i] and right[i] to get the final result.
        */

解法一

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] results = new int[len];

        int[] left = new int[len];
        int[] right = new int[len];

        left[0] = 1; // Initialize the first element of left to be 1 cuz there is no number on the left of nums[0].
        // Calculate the left product
        for (int i = 1; i < len; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }

        right[len -1] = 1;
        for (int i = len - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < len; i++) {
            results[i] = right[i] * left[i];
        }

        return results;
    }
}

解法二

上个解法的时间复杂度是 O(n), 空间复杂度也是 O(n)。这个解法的目的是为了减少空间复杂度到 O(1)。
既然我们已经能把一个数字左边的乘法结果算出来，那么可以将右边的乘法结果直接乘到左边的结果得出最终结果。
Keep tracking the product on the right of a number and keep updating the results.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] results = new int[len];

        results[0] = 1; // Initialize the first element of left to be 1 cuz there is no number on the left of nums[0].
        // Calculate the left product
        for (int i = 1; i < len; i++) {
            results[i] = results[i - 1] * nums[i - 1];
        }

        int right = 1;
        for (int i = len - 1; i >= 0; i--) {
            results[i] = results[i] * right;
            right *= nums[i];
        }

        return results;
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接