構(gòu)建乘積數(shù)組

題目：給定一個(gè)數(shù)組 A[0,1,…,n-1]，請(qǐng)構(gòu)建一個(gè)數(shù)組 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]，不能使用除法。

解題思路

例如：

A[]={1,2,3}求B[]

B[0]=A[1]×A[2]=2×3=6

B[1]=A[0]×A[2]=1×3=3

B[2]=A[0]×A[1]=1×2=2

1. B[0]初始化為 1，從下標(biāo) i=1 開始，先求出 C[i]的值并放入 B[i],即 B[i]=C[i]=C[i-1]×A[i-1]，所以 B[1]=B[1-1]×A[1-1]=B[0]×A[0]=1×1=1，i++
2. B[2]=B[2-1]×A[2-1]=B[1]×A[1]=1×2=2，i++超出長(zhǎng)度停止循環(huán)
3. C[i]計(jì)算完畢求 D[i],設(shè)置一個(gè)臨時(shí)變量 temp 初始化為 1
4. 從后往前變量數(shù)組，LengthA=3 初始化 i=LengthA-2=1，結(jié)束條件為 i>=0
5. 第一次循環(huán)，temp=temp×A[i+1]=1×A[2]=3，計(jì)算出A中最后一個(gè)元素的值放入 temp，temp 相當(dāng)于 D[i]的值
6. 因?yàn)橹暗?B[i]=C[i]，所以讓 B[i]×D[i] 就是要保存的結(jié)果，即 B[i]=B[1]=B[1]×temp=1×3=3,i–=0
7. 計(jì)算 B[i]=B[0]，temp上一步中的值是A[2]，在這次循環(huán)中 temp=temp×A[0+1]=A[2]×A[1]=3×2=6
8. B[i]=B[0]=B0]×temp=1×6=6，i–<0循 環(huán)結(jié)束

所以 B 數(shù)組為{6,3,2}

代碼實(shí)現(xiàn)

import java.util.Arrays;
public class Test52 {
    public static double[] multiply(double[] data) {
        if (data == null || data.length < 2) {
            return null;
        }
        double[] result = new double[data.length];
        // result[0]取1
        result[0] = 1;
        for (int i = 1; i < data.length; i++) {
            // 第一步每個(gè)result[i]都等于于data[0]*data[1]...data[i-1]
            // 當(dāng)i=n-1時(shí)，此時(shí)result[n-1]的結(jié)果已經(jīng)計(jì)算出來(lái)了【A】
            result[i] = result[i -1] * data[i - 1];
        }
        // tmp保存data[n-1]*data[n-2]...data[i+1]的結(jié)果
        double tmp = 1;
        // 第二步求data[n-1]*data[n-2]...data[i+1]
        // 【A】result[n-1]的結(jié)果已經(jīng)計(jì)算出來(lái)，所以從data.length-2開始操作
        for (int i = data.length - 2; i >= 0; i--) {
            tmp *= data[i + 1];
            result[i] *= tmp;
        }
        return result;
    }
    public static void main(String[] args) {
        double[] array1 = {1, 2, 3, 4, 5};
        System.out.println(Arrays.toString(multiply(array1))); // double expected[] = {120, 60, 40, 30, 24};
        double[] array2 = {1, 2, 0, 4, 5};
        System.out.println(Arrays.toString(multiply(array2))); // double expected[] = {0, 0, 40, 0, 0};
        double[] array3 = {1, 2, 0, 4, 0};
        System.out.println(Arrays.toString(multiply(array3))); // double expected[] = {0, 0, 0, 0, 0};
        double[] array4 = {1, -2, 3, -4, 5};
        System.out.println(Arrays.toString(multiply(array4))); // double expected[] = {120, -60, 40, -30, 24};
        double[] array5 = {1, -2};
        System.out.println(Arrays.toString(multiply(array5))); // double expected[] = {-2, 1};
    }
}

運(yùn)行結(jié)果

http://wiki.jikexueyuan.com/project/for-offer/images/70.png" alt="" />