当前位置：首页 > article >正文

力扣最热一百题——除自身以外数组的乘积

article 2024/9/21 22:00:21

题目链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：左右数组（小型动态规划）

实现思路

Java写法：

运行时间

C++写法：

运行时间

时间复杂度以及空间复杂度

总结

题目链接：238. 除自身以外数组的乘积 - 力扣（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) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

解法一：左右数组（小型动态规划）

这个问题可以通过两次遍历数组来解决，而不需要使用额外的空间（除了用于结果的数组之外），但这段代码巧妙地使用了两个辅助数组 left 和 right 来分别存储每个元素左侧所有元素的乘积和右侧所有元素的乘积，从而避免了在单次遍历中同时计算左右两侧乘积的复杂性。

实现思路

初始化：
- 首先，创建一个与输入数组 nums 长度相同的数组 left，用于存储每个元素左侧所有元素的乘积（包括元素本身位置为1的情况，因为元素本身不参与计算）。
- 同时，创建一个与 nums 长度相同的数组 right，用于存储每个元素右侧所有元素的乘积（同样，元素本身位置为1）。
计算左侧乘积：
- 遍历 nums 数组，从左到右。
- 对于 left 数组的每个位置 i，其值等于 nums[i-1]（如果 i > 0）与 left[i-1] 的乘积。如果 i = 0，则 left[0] = 1，因为没有元素在 nums[0] 的左侧。
计算右侧乘积：
- 遍历 nums 数组，但这次是从右到左。
- 对于 right 数组的每个位置 i，其值等于 nums[i+1]（如果 i < len-1）与 right[i+1] 的乘积。如果 i = len-1，则 right[len-1] = 1，因为没有元素在 nums[len-1] 的右侧。
计算最终结果：
- 再次遍历 nums 数组，这次是为了计算每个元素的最终结果。
- 对于 nums 数组的每个位置 i，其最终值等于 left[i]（左侧所有元素的乘积）与 right[i]（右侧所有元素的乘积）的乘积。
返回结果：
- 将修改后的 nums 数组返回，此时 nums 数组的每个元素都已经是除了它自身以外所有元素的乘积了。

Java写法：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        if(len == 0){
            return nums;
        }
        // 定义出两个数组分别表示左边的乘积和右边数组的乘积
        // 这个思路有点和动态规划相似
        //       0  1  2 3
        //       1, 2, 3,4
        // left  1, 1, 2,6
        // right 24,12,4,1
        int[] left = new int[len];
        int[] right = new int[len];

        // 填入左边乘积数组的值
        // 初始化
        left[0] = 1;
        for(int i = 1; i < len ; i++){
            left[i] = nums[i - 1] * left[i - 1];
        }

        // 填入右边乘积数组的值
        right[len - 1] = 1;
        for(int i = len - 2; i >= 0 ; i--){
            right[i] = nums[i + 1] * right[i + 1];
        }

        for(int i = 0; i < len; i++){
            nums[i] = left[i] * right[i];
        }

        return nums;

    }
}

运行时间

C++写法：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();

        vector<int> left(len);
        vector<int> right(len);

        left[0] = 1;
        for(int i = 1; i < len; i++){
            left[i] = nums[i - 1] * left[i - 1];
        }

        right[len - 1] = 1;
        for(int i = len - 2; i >= 0; i--){
            right[i] = nums[i + 1] * right[i + 1];
        }

        for(int i = 0; i < len; i++){
            nums[i] = left[i] * right[i];
        }

        return nums;
    }
};