当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.238.Product of Array Except Self 除自身以外数组的乘积

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]

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


此外,还可以只使用一个left[]数组,右侧累积在从右往左构造结果res[]中动态计算。
进一步,还可以将左侧累积保存到输出数组中来节省空间开销。

private static class SolutionV2020 {
    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;
    }
}

GitHub代码

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


上一篇 LeetCode.392.Is Subsequence 判断是否子序列

下一篇 LeetCode.697.Degree of an Array 度数相同的最小连续子数组

阅读
评论
372
阅读预计2分钟
创建日期 2020-02-08
修改日期 2020-02-08
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论