目录
题目描述:
示例:
解法:
题目描述:
给定长度为 n 的整数数组 nums, 其中 n> 1, 返回输出数组 output , 其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积.
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法, 且在 O(n) 时间复杂度内完成此题.
进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的, 输出数组不被视为额外空间.)
解法:
- class Solution {
- public:
- vector<int> productExceptSelf(vector<int>& nums) {
- int sz = nums.size();
- vector<int> left(sz+1, 1);
- vector<int> right(sz+1, 1);
- for(int i = 0; i <sz; i++){
- left[i+1] = left[i] * nums[i];
- }
- for(int j = sz-1; j>= 0; j--){
- right[j] = right[j+1] * nums[j];
- }
- vector<int> res;
- for(int i = 0; i < sz; i++){
- res.push_back(left[i]*right[i+1]);
- }
- return res;
- }
- };
来源: http://www.bubuko.com/infodetail-3073756.html