【LC中等】238. 除自身以外数组的乘积

Love The Way You Lie 2023-09-27 09:56 64阅读 0赞

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨**博客主页:**[ **XIN-XIANG荣**][_XIN-XIANG]  
✨**系列专栏:**[**【LeetCode/牛客刷题】**][LeetCode]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  题目描述:
 *  解题思路：
 *  代码实现：
 *  提交结果：

## 题目描述: ##

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

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

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

**示例 1:**

输入: nums = \[1,2,3,4\]

输出: \[24,12,8,6\]

**示例 2:**

输入: nums = \[-1,1,0,-3,3\]

输出: \[0,0,9,0,0\]

**提示：**

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

**进阶：** 你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

来源：力扣（LeetCode）

链接：[https://leetcode.cn/problems/product-of-array-except-self][https_leetcode.cn_problems_product-of-array-except-self]

## 解题思路： ##

题目中要求不能使用除法，也就是求出所有元素的乘积再进行除法运算这种方法是不可行的；那么换一种思路只要求出除nums\[i\]之外其他各元素的乘积即可，我是可以实现分别计算出nums\[i\]左边的元素的乘积和其右边元素的乘积，这样两边的元素的乘积再相乘便可得到想要的结果；

我们可以创建两个数组left和right分别存放nums中每个元素对应左边和右边元素的乘积，再将这两个数组中对应元素相乘得到结果再放入要返回的数组当中；这里时间和空间复杂度都为O(N);

要注意对于下标为 ‘0’和’len-1’ 的元素，因为左侧和右侧没有元素，所以0下标左边所有元素的乘积和 len-1 下标右边的元素应该赋值为1

对上面的做法可以进行优化，我们把要返回的数组answer当作上面的left数组先计算出每个元素左边所有元素的乘积放到answer中，而righ(右边元素的乘积)可以通过循环来计算出来再乘在answer的元素当中得到结果，相比上面的做法不用再开辟另外两个数组，时间复杂度为O(N)，空间复杂度为O(1)。

## 代码实现： ##

class Solution {
        
        //方法一
        /*public int[] productExceptSelf(int[] nums) {
            int len = nums.length;
            //left 和 right 分别表示左右两侧的乘积列表
            int[] left = new int[len];
            int[] right = new int[len];
            //要返回的数组
            int[] answer = new int[len];
            
            //对于下标为 '0'和'len-1' 的元素，因为左侧和右侧没有元素，所以赋值为1
            left[0] = 1;
            right[len-1] = 1;
            
            //left[i] 为下标 i 左侧所有元素的乘积
            //right[i] 为下标 i 右侧所有元素的乘积
            int i = 0;
            for(i = 1; i <= len-1; i++) {
                left[i] = left[i-1]*nums[i-1];
                right[len-1-i] = right[len-i]*nums[len-i];
            }
    
            // 对于下标 i，除 nums[i] 之外其余各元素的乘积
            //就是左侧所有元素的乘积乘以右侧所有元素的乘积
            for(i = 0; i < len; i++) {
                answer[i] = left[i]*right[i];
            }
            return answer;
        }*/
    
        //方法二：对方法一进行优化
        public int[] productExceptSelf(int[] nums) {
        
            int len = nums.length;
            int[] answer = new int[len];
            
            answer[0] = 1;
            
            int i = 0;
            for(i = 1; i <= len-1; i++) {
        
                answer[i] = nums[i -1] * answer[i-1];
            }
            
            int right = 1;
            for(i = len-1; i >= 0; i--) {
        
                answer[i] = answer[i]*right;
                right *= nums[i];
            }
            return answer;
        }
        
    }

## 提交结果： ##

![img][]

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[LeetCode]: https://blog.csdn.net/trong_/category_11990219.html?spm=1001.2014.3001.5482
[https_leetcode.cn_problems_product-of-array-except-self]: https://leetcode.cn/problems/product-of-array-except-self
[img]: https://img-blog.csdnimg.cn/img_convert/c84caa7b5150dda0aae88ca84f03143f.png