[Leetcode] Product of Array Except Self 自身以外的数组乘积

rockswang 发布于2019-08-14 12:34 / 1257人阅读

摘要：动态规划复杂度时间空间思路分析出自身以外数组乘积的性质，它实际上是自己左边左右数的乘积，乘上自己右边所有数的乘积。所以我们可以用一个数组来表示第个数字前面数的乘积，这样。同理，我们可以反向遍历一遍生成另一个数组。

Product of Array Except Self

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

动态规划 复杂度

时间 O(N) 空间 O(N)

思路

分析出自身以外数组乘积的性质，它实际上是自己左边左右数的乘积，乘上自己右边所有数的乘积。所以我们可以用一个数组left[i]来表示第i个数字(nums[i])前面数的乘积，这样left[i] = left[i-1] nums[i-1]。同理，我们可以反向遍历一遍生成另一个数组right[i] = right[i + 1] nums[i+1]。得到这两个数组后，我们再遍历一遍，把每个位置的left[i]乘上right[i]就行了

双向遍历法 复杂度

时间 O(N) 空间 O(1)

思路

实际上，我们可以用结果数组自身来存储left和right数组的信息。首先还是同样的算出每个点左边所有数的乘积，存入数组中。然而在反向算右边所有数的乘积时，我们不再把它多带带存入一个数组，而是直接乘到之前的数组中，这样乘完后结果就已经出来了。另外，因为我们不再多带带开辟一个数组来存储右边所有数，不能直接根据数组上一个来得知右边所有数乘积，所以我们需要额外一个变量来记录右边所有数的乘积。这里为了清晰对称，遍历左边的时候也加入了一个额外变量来记录。

注意

因为第一位在第一轮从左向右乘的时候乘不到，结果数组中会得到0，所以要先将第一位置为1，即res[0] = 1，其他的不用初始化

因为涉及左右两边的数，所有数组长度为1的时候就直接返回自身就行了

代码

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if(nums.length <= 1){
            return nums;
        }
        int[] res = new int[nums.length];
        res[0] = 1;
        int left = 1, right = 1;
        // 计算每个点左边的乘积
        for(int i = 1; i < nums.length; i++){
            left = left * nums[i - 1];
            res[i] = left;
        }
        // 计算每个点右边的乘积
        for(int i = nums.length - 2; i >= 0; i--){
            right = right * nums[i + 1];
            res[i] = right * res[i];
        }
        return res;
    }
}

GPU云服务器云服务器 php数组之间乘积数组中求乘积数组array 数组Array类型

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64558.html

LeetCode 238 Product of Array Except Self

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

henry14 2019-08-14 17:43 评论0 收藏0
【Python】LeetCode 238. Product of Array Except Self

摘要：题目描述题目解析简单来说就是对于数组中每一项，求其他项之积。算一遍全部元素的积再分别除以每一项要仔细考虑元素为零的情况。没有零直接除下去。一个零零的位置对应值为其他元素之积，其他位置为零。两个以上的零全部都是零。题目描述 Given an array of n integers where n > 1, nums, return an array output such that o...

kaka 2019-07-31 12:22 评论0 收藏0
[LeetCode] Product of Array Except Self

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

golden_hamster 2019-08-16 11:14 评论0 收藏0
[LeetCode] 238. Product of Array Except Self

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

Loong_T 2019-08-14 14:32 评论0 收藏0
leetcode 628 Maximum Product of Three Numbers

摘要：题目详情输入一个大小大于等于三的数组，给出其中任意三个数乘积中的最大乘积想法这道题最主要的是要考虑正负数的情况。如果全都是正数相乘比较大，就取三个最大值相乘即可。题目详情 Given an integer array, find three numbers whose product is maximum and output the maximum product.输入一个大小大于...

CoreDump 2019-08-15 13:57 评论0 收藏0