Yuan
0%

238. Product of Array Except Self

Posted on

method1: division

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def productExceptSelf(self, A: List[int]) -> List[int]:
        P=1
        N=len(A)
        k=0
        for i in range(N):
            if A[i]==0:
                k+=1
            else:
                P=P*A[i]
        ans=[0]*N
        for i in range(N):
            if k>=2:
                P=0
            elif k==1:
                print(A[i])
                if A[i]==0:
                    ans[i]=P
                else:
                    ans[i]=0
            else:
                ans[i]=P//A[i]
        return ans

method2: hash: space O(n) without division

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def productExceptSelf(self, A: List[int]) -> List[int]:
        L={}
        R={}
        N=len(A)
        ans=[0]*N
        P=1
        for i in range(N):
            P=P*A[i]
            L[i]=P
        P=1
        for i in range(N-1,-1,-1):
            P=P*A[i]
            R[i]=P
        for i in range(N):
            curr=1
            if i-1>=0:
                curr*=L[i-1]
            if i+1<N:
                curr*=R[i+1]
            ans[i]=curr
        return ans

method3: improve the method 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def productExceptSelf(self, A: List[int]) -> List[int]:
        N=len(A)
        ans=[0]*N
        LP=1
        for i in range(N):
            LP*=A[i]
            ans[i]=LP
        RP=1
        for i in range(N-1,-1,-1):
            #right part
            curr=RP
            RP*=A[i]
            #left part
            if i-1>=0:
                curr*=ans[i-1]
            ans[i]=curr
        return ans