【剑指offer】51.构建乘积数组

51.构建乘积数组

知识点：数组；

题目描述

给定一个数组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无意义，故而无法构建，因此该情况不会存在。

解法一:

可以发现对于B[i],就是把A中数组元素全部乘一次，然后除以A[i]，但是题目中不能用除法，所以可以每次先将A[i]的值赋为1，然后再去相乘；

public class Solution {

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

        int[] B = new int[A.length];

        int temp;

        for(int i = 0; i < A.length; i++){

            int count=1;

            temp = A[i];  //临时把A[i]的值存起来，这一轮结束后再还给A[i];

            A[i] = 1;

            for(int j = 0; j < A.length; j++){

                count *= A[j];

            }

            A[i] = temp;

            B[i] = count;

        }

        return B;

    }

}

这样去解用了for的嵌套，时间复杂度为O(n^2);其实可以发现我们每次都要去将这么多元素的值去乘一遍，每次只有一个元素不一样，这样太浪费了，所以有了下面这样的解法。

解法二：

经过上述分析后可以得到下图，其实就是将求B中第i个元素的值，那就是让A中的第i个元素值为1

算每行的Bi就是将这行所有的元素乘一下就可以了，可以发现在左下角，在算B[i的时候，其实是要用到B[i-1]的，它们的关系是B[i]=B[i-1]*A[i-1];再看右上角，从下往上，假设值为temp吧，那temp[i]=temp[i+1] *A[i+1];然后再把左边和右边相乘就可以了。

public class Solution {

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

        int[] B = new int[A.length];

        B[0] = 1;

        int temp = 1;

        for(int i = 1; i < A.length; i++){

            B[i] = B[i-1] * A[i-1]; //计算左下角；

        }

        for(int j = A.length-2; j >= 0; j--){

            temp *= A[j+1];  //计算右下角和整个B；

            B[j] *= temp;

        }

        return B;

    }

}

这样利用到了先前的信息，减少了浪费，时间复杂度为O(n);

巴特西

【剑指offer】51.构建乘积数组

51.构建乘积数组

题目描述

解法一:

解法二：

最新文章

热门文章