您现在的位置是:首页 >其他 >图解LeetCode——238. 除自身以外数组的乘积网站首页其他

图解LeetCode——238. 除自身以外数组的乘积

爪哇缪斯 2024-06-17 06:01:02
简介图解LeetCode——238. 除自身以外数组的乘积

一、题目

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

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

二、示例

2.1> 示例 1:

输入】 nums = [1,2,3,4]
输出】 [24,12,8,6]

2.2> 示例 2:

输入】 nums = [-1,1,0,-3,3]
输出】 [0,0,9,0,0]

提示:

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

三、解题思路

根据题目要求,我们需要计算出数组nums中,每个元素除自己之外的乘积值,即假设nums包含4个元素,分别为nums[0]~`nums[3]`,那么最终结果如下所示:

nums[0] = nums[1] * nums[2] * nums[3]
nums[1] = nums[0] * nums[2] * nums[3]
nums[2] = nums[0] * nums[1] * nums[3]
nums[3] = nums[0] * nums[1] * nums[2]

但是如果按照上面计算我们会发现一个问题,就是会出现很多重复计算,比如我们计算nums[0]nums[1]的时候,针对nums[2] * nums[3]这部分就是重复计算的。所以,为了解决这个问题,我们可以看下面这个图,在这个图中白色的格子表示不参与计算,那么正好可以分割为左下角右上角两部分数字集合,具体情况请见下图所述:

针对上面的分析,我们可以分为两部分对数组nums进行计算操作:

【正向遍历数组】 这种遍历方式,我们可以来计算左下角的数字乘积;
【逆向遍历数组】 这种遍历方式,我们可以来计算右上角的数字乘积(用temp保存),然后与左下角再执行相乘操作;

好了,如上就是本题的解题思路了,为了便于大家理解,我们以nums = [1,2,3,4]为例,看一下具体的操作过程。请见下图所示:

四、代码实现

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length, temp = 1;
        int[] result = new int[n];
        result[0] = 1;
        for (int i = 1; i < n; i++) 
            result[i] = result[i-1] * nums[i-1]; 
        for (int i = n - 2; i >= 0; i--) {
            result[i] *= temp * nums[i+1];
            temp *= nums[i+1];
        }
        return result;
    }
}

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ (^o^)/ ~ 「干货分享,每天更新」

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。