X

LEETCODE 238. Product of Array Except Self 解题思路分析

题目大意:

除自身以外数组的乘积

给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

说明: 不要使用除法,且在 O(n) 时间复杂度内完成此题。

进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=238

解题思路分析:

本题最初想到的思路是先得到所有数的乘积,然后在计算每个数字左右两侧所有数乘积时,用总的乘积除以自身即可。但本题明确要求不能使用除法,所以该解法不可行,另外这种解法也存在一个漏洞,如果数组中存在0,那么该解法就无能为力了。比如[5,0,8],所有数字乘积为0,虽然对于5和8没影响,但数字0,首先它自身无法作为除数,另外,其它数的乘积我们也无从获知。

所以本题需要使用到前缀乘积的方式来解题,这个思路非常类似之前多次介绍过的前缀和数组思路。我们维护两个数组,事先求出每一位数字左边所有数的乘积(前缀乘积),以及右边所有数的乘积(后缀乘积),然后对于当前位,左边乘积乘以右边乘积即是当前答案。

另外,本题要求除了返回结果外,只能使用常量级别的内存空间,即空间复杂度要求在O(1),因此,我们可以使用返回结果的数组临时作为前缀乘积数组,后缀乘积我们使用一个变量来迭代即可。

实现代码:

public int[] productExceptSelf(int[] nums) {
    // 返回结果
    int[] res = new int[nums.length];
    // 现将返回结果数组作为前缀乘积数组
    // 第0位左边没有数字,因此它左边数字乘积为1
    res[0]=1;
    // 计算每一位的前缀乘积
    for(int i=1;i<nums.length;i++){
        // 当前位的前缀乘积等于前一位前缀乘积乘以前一位数字
        res[i]=res[i-1]*nums[i-1];
    }
    // 动态迭代结算后缀乘积,最后一位不存在右侧数字,
    // 后缀乘积为1
    int leftProduct =1;
    // 从最后一位循环数组
    for(int i=nums.length-1;i>=0;i--){
        // 计算每一位的后缀乘积
        leftProduct*= i<nums.length-1?nums[i+1]:1;
        // 当前位的前缀乘积乘以后缀乘积即是当前位答案
        res[i]*=leftProduct;
    }
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.

Memory Usage: 47.7 MB, less than 5.51% of Java online submissions for Product of Array Except Self.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-238-product-of-array-except-self-解题思路分析/
Categories: leetcode
kwantong: