中国建设银行合肥招聘信息网站,网站建设 网页,南昌网站设计制作,重庆系统建站怎么用一.题目要求
给你一个整数数组 nums#xff0c;返回 数组 answer #xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 **不要使用除法#xff0c;**且在…一.题目要求
给你一个整数数组 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) 的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组 不被视为 额外空间。
四.解题思路
详见代码
五.代码实现
//考虑到不用除法的情况, 可以认为每个位置的ans[i]应当为其左边所有数的乘积乘右边所有数的乘积
//因此我们可以先声明答案数组ans, 遍历一遍求出每个ans[i],表示第i个元素及其后i个元素的乘积
//而后更新nums, 新的nums[i]表示第i个元素及其前i个元素的乘积
//而后在更新一次ans, 此时ans[i] ans[i 1] * nums[i - 1] 即可表示该位置的结果(第一个和末尾数特判即可)
class Solution {
public:vectorint productExceptSelf(vectorint nums) {vectorint ans(nums.size(), 0);int n nums.size();*ans.rbegin() *nums.rbegin();for (int i n - 2; i 0; i--) {ans[i] nums[i] * ans[i 1];}for (int i 1; i n; i) {nums[i] nums[i - 1] * nums[i];}for (int i 0; i n; i) {if (i 0)ans[i] ans[i 1];else if (i n - 1)ans[i] nums[i - 1];else {ans[i] nums[i - 1] * ans[i 1];}}return ans;}
};六.题目总结
–
