一、题目描述

  【JZ51】给定一个数组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];）
  知识点：数组
  难度：☆java

二、解题思路

  根据题目描述，若是可使用除法，就很简单。可是要求不能使用。
  假设：
  left[i] = A[0]*...*A[i-1]
  right[i] = A[i+1]*...*A[n-1]
  因此：
  B[i] = left[i] * right[i]
  这样就避免使用了除法。可是若是对每一个B[i], 0<=i<n,都这么求，显然时间复杂度过高。
  把整个结果画到下面图：

  可知：
  left[i+1] = A[0]*...A[i-1]*A[i]
  right[i+1] = A{i+2]*...*A[n-1]
  因而，
  left[i+1] = left[i] * A[i]
  right[i] = right[i+1] * A[i+1]
  因此，能够先把全部的left[i]求出，right[i]求出。web

三、解题代码

package pers.klb.jzoffer.simple;

/** * @program: JZoffer * @description: 构建乘积数组 * @author: Meumax * @create: 2020-06-17 10:31 **/
public class ArrayProduct {

    public int[] multiply(int[] A) {

		// 建立数组B
        int[] B = new int[A.length];

		// 初始化第一个元素为1
        B[0] = 1;

  		// 计算 left
        for (int i = 1; i < A.length; i++) {
            B[i] = B[i - 1] * A[i - 1];
        }

        int temp = 1;

		// 计算 right 并乘以 left 获得最终的 B
        for (int j = A.length - 2; j >= 0; j--) {
            temp = temp * A[j + 1];
            B[j] = B[j] * temp;
        }

        return B;
    }
}

  时间复杂度：O(N)
  空间复杂度: O(1)数组

四、解题心得

  虽然这道题的难度为一颗星，并且我看到题目是的第一反应也是写成下面这样：svg

package pers.klb.jzoffer.simple;

/** * @program: JZoffer * @description: 构建乘积数组 * @author: Meumax * @create: 2020-06-17 10:31 **/
public class ArrayProduct {

    public int[] multiply(int[] A) {
        int length = A.length;
        int[] B = new int[length];
        for(int i=0;i<length;i++){
            B[i] = mulWithoutIndex(A,i);
        }
        return B;
    }

    public int mulWithoutIndex(int[] A,int index){
        int result = 1;

        for(int i = 0;i<A.length;i++){
            if(i == index){
                continue;
            }else{
                result *= A[i];
            }
        }

        return result;
    }
}

  思路极其简单，潜意识就蹦出来了：对于B的每个元素B[i]，计算乘积的时候只须要把对应位置的A[i]跳过去就好了。
  后来一分析本身的这个写法，问题就出在时间复杂度上，本身没有意识到其实本身写出了双层嵌套的for循环，也就是说时间复杂度达到了O(N²)，这是不行的，由于有优化空间。优化