题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。（注意：规定B[0] = A[1] A[2] … A[n-1]，B[n-1] = A[0] A[1] … A[n-2];）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

解法

如果能用除法我将绝杀，可惜用不得🙃。先用暴力法，能通过再说。

1. 暴力法

题目要求B中的元素等于A的所有元素相乘但不乘A的对应索引的元素。

例如 B[2] = A[0]*A[1]*A[3]*…*A[n-1]

则可以使用双重循环算出每一个B的值，再放入B中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {

  public int[] multiply(int[] A) {
    if (A == null || A.length <= 1) {
      return null;
    }
    // 初始化数组
    int[] B = new int[A.length];
    for (int i = 0; i < B.length; i++) {
      int product = 1;
      for (int j = 0; j < A.length; j++) {
        if (i != j) {
          product *= A[j];
        }
      }
      B[i] = product;
    }
    return B;
  }

}

时间复杂度为$O(n^2)$，空间复杂度为$O(1)$

2. 找规律

暴力法的时间复杂度实在是太高了，数据量一大就很费时间，所以找寻题目中的规律，换个方法做。

通过看上面这个图可以发现，B的值是由左边和右边乘起来的，而左边的规律是

left[i + 1] = left[i] * A[i + 1]

同样地，右边也是如此。

我们可以先用循环把所有B的left值算出来，再计算right的值乘起来就可以了。

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
public class Solution {

  public int[] multiply(int[] A) {
    if (A == null || A.length <= 1) {
      return null;
    }
    int len = A.length;
    // 新建B并初始化B
    int[] B = new int[len];
    for (int i = 0; i < len; i++) {
      B[i] = 1;
    }
    int left = 1, right = 1;
    // 从B[1]开始计算left
    for (int i = 1; i < len; i++) {
      left *= A[i - 1];
      B[i] = left;
    }
    // 从B[n-2]开始计算right
    for (int j = len - 2; j >= 0; j--) {
      right *= A[j + 1];
      B[j] *= right;
    }
    return B;
  }

}

时间复杂度为$O(n)$，空间复杂度为$O(1)$

参考