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

目录

题目链接：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 来分别存储每个元素左侧所有元素的乘积和右侧所有元素的乘积，从而避免了在单次遍历中同时计算左右两侧乘积的复杂性。

实现思路

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

运行时间

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

---

总结

        累了哥几个，最近有点焦虑了，不总结了哎