剑指Offer的学习笔记（C#篇） 构建乘积数组

题目描述

给定一个数组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]。不能使用除法。

一 . 题目解析

        简而言之，给你一个数组，返回一个数组，返回的数组内容不包含A[i]，注意题目中红色部分。也就是说，你返回的这个数组B，他的每一项都是数组A中除了A[i]之外内容的乘积。

二 . 解题过程

        思想是这样的：看下图，B₀ = A₁*A₂*A₃*……A_n-1；（无A₀）

                                                B₁ = A₀*A₂*A₃*……A_n-1；（无A₁）

                                                                  ----

                                                B_n-1 = A₀*A₂*A₃*……A_n-2；（无A_n-1）

        这个时候呢，看下图，我们就把B₀至B_n-1都表示出来了；表面上看上去不是很难，但是如何用代码实现呢，这样，因为B上的每一个元素都是不含B[i]的连乘，如果B中每个数都等于B_i =（A₀*A₁*A₂*……A_n-1）/（A_i），是不是很方便呢，but！！题目要求不让用除法，但是不用除法，这个A_i不好摘出来，所以，这时候，看下图，把灰色部分当成分界线，再使用连乘，就变成了左右两部分，然后最后左右再相乘，就实现了我们的目标，具体看代码，更加直观，（我现在在吃包子，之前吃了一个冰激凌，好腻啊！！）

二 . 代码实现

class Solution
{
    public int[] multiply(int[] A)
    {
        // write code here
        //定义数组A的长度为n
        int n = A.Length;
        //定义一个新的数组B
        int [] B = new int [n];
        //设置B[0]为1
        B[0] = 1 ;
        //创建左循环
        for(int i=1 ; i<n ; i++)
        {
            B[i] = B[i-1]*A[i-1];
        }
        //创建右循环
        int x = 1;
        for(int i = n - 2; i >= 0; i--)
        {
            x = x * A[i+1];
            B[i] *= x;
        }
        //得出新数组B
        return B;
    }
}