24
07/2015
[LeetCode] Product of Array Except Self
Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
解题思路：
这道题的题意为给定一个数组A，求数组B，其中B为A中除对应元素外所有其他数组元素的乘积。
要求不能用除法，而且时间复杂度为O(n)
解法1：倘若用除法，先求出A中所有元素的乘积，然后将积除以对应元素。注意讨论是否为0。且本题不许用除法。
解法2：B中的元素等于对应元素A中所有左边元素的乘积*A中所有右边元素的乘积。可以用两个数组left、right记录所有对应元素左边和右边的乘积，然后相乘即可。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> left(len, 1); //当前元素左边的乘积
vector<int> right(len, 1); //当前元素右边的乘积
vector<int> result;
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++){
result.push_back(left[i] * right[i]);
}
return result;
}
};解法3：题意要求以空间复杂度为O（1）的方法来解决，上种解法的空间复杂度为O(n)。优化后的代码如下：
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> result(len, 1);
for(int i=1; i<len; i++){
result[i] = result[i - 1] * nums[i - 1];
}
int right = 1;
for(int i=len-2; i>=0; i--){
right *= nums[i + 1];
result[i] = result[i] * right;
}
return result;
}
};
0 条评论