当前位置 : 首页 » 文章分类 :  算法  »  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]

此外,还可以只使用一个数组 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


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

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

阅读
评论
617
阅读预计3分钟
创建日期 2020-02-08
修改日期 2020-06-04
类别

页面信息

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

评论