思路
乘积 = 当前数左边的乘积 * 当前数右边的乘积
我一开始想到了要这么去解决,但是没有想到如何用o(n) 的时间复杂度解决
看了别人的题解才明白,将这个过程分两步完成,先保留当前数左边的乘积,然后乘上当前数右边的乘积,处理两趟,就可以了。 可以从左到右遍历,就可以从右向左遍历,同时还可以将一步的过程变成两步来做,厉害哇。异步获得结果。
代码
class Solution
{
public
:
vector
<int> productExceptSelf(vector
<int>& nums
) {
if (nums
.size() == 0) return nums
;
vector
<int> ans(nums
.size(), 1);
for (int i
= 0, k
= 1; i
< nums
.size(); i
++) {
ans
[i
] = k
;
k
*= nums
[i
];
}
for (int i
= nums
.size() - 1, k
= 1; i
>= 0; i
--) {
ans
[i
] *= k
;
k
*= nums
[i
];
}
return ans
;
}
};
总结
心力憔悴,这。。