武城网站建设,wordpress获取qq头像评论,网站建设信(信科网络),网站备案公司目录
题目链接#xff1a;238. 除自身以外数组的乘积 - 力扣#xff08;LeetCode#xff09;
题目描述
示例
提示#xff1a;
解法一#xff1a;左右数组#xff08;小型动态规划#xff09;
实现思路
Java写法#xff1a;
运行时间
C写法#xff1a;
运行时…
目录
题目链接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[i1]如果 i len-1与 right[i1] 的乘积。如果 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,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:vectorint productExceptSelf(vectorint nums) {int len nums.size();vectorint left(len);vectorint 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;}
};
运行时间 时间复杂度以及空间复杂度 总结 累了哥几个最近有点焦虑了不总结了哎
