题目 :

1
2
3
4
5
6
Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B without divide operation.

Example
For A=[1, 2, 3], B is [6, 3, 2]

这种问题叫做Forward-Backward Traversal问题

思路就是对于数组中的某个数来说，既记录其前面的数据，也记录其后面的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
    * @param A: Given an integers array A
    * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
    */
   public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
       if (A == null || A.size() == 0) {
           return new ArrayList<Long>();
       }
       long[] B = new long[A.size()];
       ArrayList<Long> result = new ArrayList<Long>();
       long product = 1;
       for (int i = A.size() - 1; i >= 0; i--) {
           product *= A.get(i);
           B[i] = product;
       }
       
       product = 1;
       long forward, back;
       for (int i = 0; i < A.size(); i++) {
           if (i == A.size() - 1) {
               forward = 1;
           } else {
               forward = B[i + 1];
           }
           back = product;
           result.add(back * forward);
           product *= A.get(i);
       }
       
       return result;
   }