LeetCode.238.Product of Array Except Self 除自身以外数组的乘积

题目描述

238 Product of Array Except Self
https://leetcode-cn.com/problems/product-of-array-except-self/

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

---

解题过程

数组中每个元素以外的其他元素的乘积构成一个新的数组。
不让用除法，并且数组元素有 0 时也无法用除法。

左右乘积法，其实也就是 前缀和** 的思想，用两个数组 left[i] 和 right[i] 分别保存元素 i 左/右 所有元素的乘积，或者叫前缀积和后缀积，则 res[i] = left[i] * right[i]

此外，还可以只使用一个数组 left[] 或 right[] 保存前缀/后缀积
1、如果先计算出前缀积数组 left[]，则第二遍从右往左计算，计算过程中用一个变量 suffixProduct 累积右侧的乘积，则 res[i] = suffixProduct * left[i]
2、如果先计算出后缀积数组 right[]，则第二遍从左往右计算，计算过程中用一个变量 preProduct 累积左侧的乘积，则 res[i] = preProduct * ritht[i]
进一步，还可以将 left[] 或 right[] 数组保存到结果数组 res[] 中，将空间复杂度将为 O(1)

2020年2月

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV202002 {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        // left[i]: nums[i]左边所有元素乘积
        int[] left = new int[size];
        // right[i]: nums[i]右边所有元素乘积
        int[] right = new int[size];
        int leftProduct = 1, rightProduct = 1;
        for (int i = 0; i < size; i++) {
            left[i] = leftProduct;
            leftProduct *= nums[i];
            right[size - i -1] = rightProduct;
            rightProduct *= nums[size - i -1];
        }
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = left[i] * right[i];
        }
        return res;
    }
}

2020年6月

每天做题真的有效果，6月4日每日一题再次做这个题时，自己直接就想出来最优解了。

时间复杂度 O(n)，空间复杂度 O(1)

private static class SolutionV202006 {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        // 先将 后缀积 放入 res 中，即 res[i] = res[i+1] * ... * res[nums.length - 1]
        res[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            res[i] = nums[i + 1] * res[i + 1];
        }

        // 前缀积
        int preProduct = 1;
        for (int i = 0; i < nums.length; i++) {
            res[i] = preProduct * res[i];
            preProduct *= nums[i];
        }
        return res;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_238_ProductOfArrayExceptSelf.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_238_ProductOfArrayExceptSelf.java

---