238. Product of Array Except Self

  • 48.0%

https://leetcode.com/problems/product-of-array-except-self/#/description

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).

1
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.)


剑指offer 52

https://discuss.leetcode.com/topic/20434/o-n-time-and-o-1-space-c-solution-with-explanation

O(n) time and O(1) space C++ solution with explanation

方法一:

First, consider O(n) time and O(n) space solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> fromBegin(n);
fromBegin[0]=1;
vector<int> fromLast(n);
fromLast[0]=1;

for(int i=1;i<n;i++){
fromBegin[i]=fromBegin[i-1]*nums[i-1];
fromLast[i]=fromLast[i-1]*nums[n-i];
}

vector<int> res(n);
for(int i=0;i<n;i++){
res[i]=fromBegin[i]*fromLast[n-1-i];
}
return res;
}
};

方法二:

空间从o(n)降低到o(1)

对从前至后的部分考虑保留前一个值,得到结果。

很巧妙地方法,节省了空间。

We just need to change the two vectors to two integers and note that we should do multiplying operations for two related elements of the results vector in each loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
int fromBegin=1;
int fromLast=1;
vector<int> res(n,1);

for(int i=0;i<n;i++){
res[i]*=fromBegin;
fromBegin*=nums[i];
res[n-1-i]*=fromLast;
fromLast*=nums[n-1-i];
}
return res;
}
};

https://discuss.leetcode.com/topic/37927/how-from-o-n-to-o-1

How from O(N) to O(1)

Here is the O(N) based C++ implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
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(len, 0);
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[i]=left[i]*right[i];
return result;
}
};

How to use O(1) ?

By observing the above code, we can just for every position multiply it to its right position.

Just the idea to think reversly !

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
int left=1, right=1;
vector<int> result(n, 1);
for(int i=0; i<n; i++){
result[i]*=left;
result[n-1-i]*=right;
left*=nums[i];
right*=nums[n-1-i];
}
return result;
}
};

https://discuss.leetcode.com/topic/18877/my-c-solution-o-n-time-with-no-extra-space

My C++ solution, O(n) time with no extra space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> productExceptSelf(vector<int>& nums) {
int N = nums.size();
vector<int> res(N,1);

for(int i=0; i<N; i++){
if (i==0) res[i] = 1;
else res[i] = res[i-1]*nums[i-1];
}

int r_prod = 1;
for(int i=N-1; i>=0; i--){
res[i] *= r_prod;
r_prod *= nums[i];
}

return res;
}

https://discuss.leetcode.com/topic/18983/python-solution-accepted-o-n-time-o-1-space

Python solution (Accepted), O(n) time, O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
# @param {integer[]} nums
# @return {integer[]}
def productExceptSelf(self, nums):
p = 1
n = len(nums)
output = []
for i in range(0,n):
output.append(p)
p = p * nums[i]
p = 1
for i in range(n-1,-1,-1):
output[i] = output[i] * p
p = p * nums[i]
return output

https://discuss.leetcode.com/topic/30115/very-easy-two-passes-solution

Very easy two passes solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// two passes, O(2n)
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, 1);

for (int i = 1; i < n; ++i) {
ans[i] = ans[i-1] * nums[i-1];
}

int m = 1;
for (int i = n-1; i >= 0; --i) {
ans[i] *= m;
m *= nums[i];
}

return ans;
}
谢谢你,可爱的朋友。