郑州网站建设系统介绍,建设银行天津分行门户网站,除了做视频网站还能做什么网站,江西九江永修网站建设238 除自身以外数组的乘积
给你一个整数数组 nums#xff0c;返回数组 answer #xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。 请不要使用除法#xff0c…238 除自身以外数组的乘积
给你一个整数数组 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 n u m s . l e n g t h 1 0 5 2 nums.length 10^5 2nums.length105 − 30 n u m s [ i ] 30 -30 nums[i] 30 −30nums[i]30 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
进阶你可以在 O(1) 的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组不被视为额外空间。
思路
1常规思路——使用除法 根据题意分析可得到以下结论 若数组中含1个0元素那么除了该元素对应值为其他元素乘积其余乘积均为0只要记录该0元素位置赋值即可 若数组中含2个0元素那么输出的乘积全为0 若数组不含0元素那么每个元素对应乘积为总乘积除以该元素。 2不用除法 题目要求不使用除法那么可以使用前缀和思想只是应用到这里变成了前缀积。 根据题意得知每个元素对应乘积等于左侧元素乘积*右侧元素乘积。 那么只需计算每个元素左侧的所有元素乘积——前缀积 l ( n ) l(n) l(n) 和每个元素右侧的所有元素乘积——后缀积 r ( n ) r(n) r(n)即可。
代码
法一
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int product 1;vectorint v(nums.size());// cnt记录0元素个数pos记录唯一零元素位置int cnt 0, pos -1;for (int i 0; i nums.size(); i) {if (nums[i] ! 0) {product * nums[i];} else {pos i;cnt;}}if (cnt 1) {// 将v全部赋值为0fill(v.begin(), v.end(), 0);return v;} else if (cnt 1) {// 除了唯一零元素对应位置是其他元素乘积其他元素都是0v[pos] product;return v;} else {for (int i 0; i nums.size(); i) {v[i] product / nums[i];}return v;}}
};法二
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();// 分别记录i元素的前缀积和后缀积(不包括i)vectorint l(n), r(n), v;l[0] 1, r[n - 1] 1;for (int i 1; i n; i) {l[i] nums[i - 1] * l[i - 1];}for (int i n - 2; i 0; i--) {r[i] nums[i 1] * r[i 1];}for (int i 0; i n; i) {v.push_back(l[i] * r[i]);}return v;}
};
