题目描述
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
NOTE
Please solve it without division and in O(n).
Example1:
Input: [1,2,3,4]
Output: [24,12,8,6]
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
O(n)解题思路
- 定义 left， right数组
- left 从前往后走 1 -> len - 1 每次用前面的状态更新后面的状态 即 left[i] = left[i - 1] * nums[i - 1]
- right 从后往前走 len - 2 -> 0 也是复用 right[i] = right[i + 1] * nums[i + 1]
- 最后结果 res[i] = left[i] * right[i]
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> left(nums.size(), 1);
vector<int> right(nums.size(), 1);
vector<int> res(nums.size(), 1);
int len = nums.size();
for(int i = 1; i < len; i++){
left[i] = left[i - 1] * nums[i - 1];
}
for(int i = len - 2; i >= 0; i--){
right [i] = right[i + 1] * nums[i + 1];
}
for(int i = 0; i < len; i++){
res[i] = left[i] * right[i];
}
return res;
}
};
解题思路
- 常规思路 O(N^2) TLE
- N*N的表格 进行乘积 时间复杂度为O(n^2) 会报超时错误
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res(nums.size(), 1);
for(int i = 0; i < nums.size(); i++){
for(int j = 0; j < i; j++){
res[i] *= nums[j];
}
}
for(int i = 0; i < nums.size(); i++){
for(int j = i + 1; j < nums.size(); j++){
res[i] *= nums[j];
}
}
return res;
}
};
