大家好，又见面了，我是全栈君。
1. 问题描写叙述
给定一个n个整数的数组（
n>1
outputi
numsi
要求不用除法和时间复杂度为O(n).
2. 方法与思路
这道题假设没有除法的限制的话就非常easy了，先求全部数的乘积，然后除以
numsi
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> re;
long mul=1;
int zeroNum = 0;
for(int i=0; i < nums.size(); i++)
{
if(nums[i] != 0) mul *= nums[i];
else zeroNum++;
}
for(int i = 0; i < nums.size(); i++)
{
if(zeroNum > 1) re.push_back(0);
else if(zeroNum == 1)
{
if(nums[i] == 0) re.push_back(mul);
else re.push_back(0);
}
else
re.push_back(mul/nums[i]);
}
return re;
}
};可是题目上明白要求不能用除法，那我们得另辟蹊径了。以下以数组[1,2,3,4,5]为例，看完以下表述就明白了：
| 扫描顺序 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 从左至右 | 1 |
1×1 |
1×1×2 |
1×1×2×3 |
1×1×2×3×4 |
| 从右至左 | 1×(2×3×4×5) |
(1×1）×(3×4×5) |
(1×1×2)×(4×5) |
(1×1×2×3)×(5) |
(1×1×2×3×4)×(1) |
就是先从左至右扫描，记录前
i−1
i+1
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> re(nums.size(),1);
int i,tmp = 1;
for(i = 1; i < nums.size(); i++)
re[i] =re[i-1] * nums[i-1];
for(i = nums.size()-1; i >= 0; i--)
re[i] *= tmp,tmp *= nums[i];
return re;
}
};版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115781.html原文链接：https://javaforall.net
