哈尔滨网站建设推广,厦门建设厅查询网站,国内网站主机,idea建设完整的网站238.除自身以外数组的乘积 1、题目2、题目分析3、解题步骤4、复杂度最优解代码示例5、抽象与扩展 1、题目
给你一个整数数组 nums#xff0c;返回 数组 answer #xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意… 238.除自身以外数组的乘积 1、题目2、题目分析3、解题步骤4、复杂度最优解代码示例5、抽象与扩展 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) 的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组 不被视为 额外空间。 Related Topics 数组前缀和 2、题目分析
1、求某数据之外其余所有数据的相互处理则可提前按处理规则处理出前缀数组、后缀数组。 2、然后在求某数据外所有数据的相互处理时可O(1)时间复杂度用其前缀数组后缀数组处理出结果。
3、解题步骤
1、处理出前缀数组、后缀数组。 2、这样在求某数据外所有数据的相互处理时可O(1)时间复杂度用其前缀数组后缀数组处理出结果。
4、复杂度最优解代码示例 public int[] productExceptSelf(int[] nums) {int[] res new int[nums.length];// k为该数左边的乘积。int k 1;for (int i 0; i res.length; i) {res[i] k;// 此时数组存储的是除去当前元素左边的元素乘积k * nums[i];}// k为该数右边的乘积。k 1;for (int i res.length - 1; i 0; i--) {res[i] * k;// 此时数组等于左边的 * 该数右边的。k * nums[i];}return res;}
5、抽象与扩展
求某数据之外其余所有数据的相互处理则可提前按处理规则处理出前缀数组、后缀数组。
