LeetCode_左右乘积列表_中等_238.除自身以外数组的乘积

古城微笑少年丶 2023-10-06 22:45 6阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 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

## 2.思路 ##

（1）左右乘积列表  
思路参考[本题官方题解][Link 1]。

（2）原地修改  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————左右乘积列表
    class Solution {
        
        public int[] productExceptSelf(int[] nums) {
        
            int length = nums.length;
            // answer 存储最终结果
            int[] answer = new int[length];
            /*
                left 和 right 分别代表左右两侧的乘积列表
                left[i] 为索引 i 左侧所有元素的乘积
                right[i] 为索引 i 右侧所有元素的乘积
            */
            int[] left = new int[length];
            int[] right = new int[length];
            //索引为 0 的元素的左侧没有元素，故设置 left[0] = 1
            left[0] = 1;
            for (int i = 1; i < length; i++) {
        
                left[i] = left[i - 1] * nums[i - 1];
            }
            //索引为 length - 1 的元素的右侧没有元素，故设置 left[length - 1] = 1
            right[length - 1] = 1;
            for (int i = length - 2; i >= 0; i--) {
        
                right[i] = right[i + 1] * nums[i + 1];
            }
            //对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
            for (int i = 0; i < length; i++) {
        
                answer[i] = left[i] * right[i];
            }
            return answer;
        }
    }

//思路2——原地修改
    class Solution {
        
        public int[] productExceptSelf(int[] nums) {
        
            int n = nums.length;
            int[] res = new int[n];
            res[0] = 1;
            for (int i = 1; i < n; i++) {
        
                res[i] = res[i - 1] * nums[i - 1];
            }
            int rProduct = nums[n - 1];
            for (int i = n - 2; i >= 0; i--) {
        
                res[i]*= rProduct;
                rProduct *= nums[i];
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/product-of-array-except-self/solution/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode-/