永川区网站建设咨询,平面设计手机作图软件,配置wordpress七牛,做网站的优势有哪些文章目录 #x1f377;1. 题目#x1f378;2. 算法原理#x1f365;解法一#xff1a;暴力求解#x1f365;解法二#xff1a;前缀和#xff08;积#xff09; #x1f379;3. 代码实现 #x1f377;1. 题目 题目链接#xff1a;238. 除自身以外数组的乘积 - 力扣1. 题目2. 算法原理解法一暴力求解解法二前缀和积 3. 代码实现 1. 题目 题目链接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) 的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组 不被视为 额外空间。
2. 算法原理
本题的意思是要求出除了当前下标位置其他位置的乘积 解法一暴力求解
暴力求解就是遍历整个数组然后再遍历一次除了当前位置的其他位置元素乘积整个的时间复杂度为O(n2)
解法二前缀和积
这里求除了当前位置的整个数组的乘积可以理解为求前面一部的前缀积后面一部分的后缀积 预处理
f表示前缀积f[i]表示[0,i-1]区间内所有元素的乘积f[i] f[i-1] * nums[i-1]g表示后缀积g[i]表示[i1,n-1]区间内所有元素的乘积g[i] g[i1] * nums[i1] 这里因为f[i]的区间是[0,i-1]所以这里的i实际上是i-1 使用预处理之后的数组
有了预处理的数组我们只需让f[i]*g[i]即可求出当前位置的值 细节问题 这里因为要求的是乘积所以f[0]这里要提前处理一下f[0] 1同理g[n-1] 1。 f是从前往后g是从后往前 这个时间复杂度为O(n)O(n)O(n)可理解为O(n) 这里进阶是空间复杂度为O(1)求解采用的也是前缀积和后缀积用ret先装前缀积然后从后往前乘以后缀积。 我们前面采用2个数组装前缀积和后缀积可以理解得更清晰一些。 3. 代码实现
class Solution {
public:vectorint productExceptSelf(vectorint nums){int n nums.size();vectorint f(n) , g(n);//预处理前缀积f[0] 1;g[n-1] 1;for(int i1;in;i)f[i] f[i-1] * nums[i-1];//预处理后缀积for(int in-2;i0;i--)g[i] g[i1] * nums[i1];vectorint ret(n);for(int i0;in;i)ret[i]f[i]*g[i];return ret;}
};优化空间复杂度
class Solution {
public:vectorint productExceptSelf(vectorint nums){int n nums.size();vectorint ret(n,1);int left 1;for(int i1;in;i){left * nums[i-1];ret[i] left;}int right 1;for(int in-2;i0;i--){right*nums[i1];ret[i]*right;}return ret;}
};
