LintCode Q50 Product of Array Exclude Itself in Python

  • Jinhai ZHOU
  • 2 Minutes
  • 2016年12月18日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
"""
@param A: Given an integers array A
@return: An integer array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
"""
def productExcludeItself(self, A):
# write your code here
# time complexity: O(n)
# space complexity: O(n)
help_array = [1] * len(A) # suffix multiply
for i in xrange(len(A)-2, -1, -1):
help_array[i] = help_array[i + 1] * A[i + 1]
B = []
multiply = 1
for i in xrange(len(A)):
B.append(multiply * help_array[i])
multiply *= A[i]
return B
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。