【leetcode】238. 除自身以外数组的乘积

it2022-06-25  87

思路

乘积 = 当前数左边的乘积 * 当前数右边的乘积

我一开始想到了要这么去解决,但是没有想到如何用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; } };

总结

心力憔悴,这。。


最新回复(0)