剑指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]之外内容的乘积。

二 . 解题过程

思想是这样的：看下图，B0 = A1*A2*A3*……An-1；（无A0）

B1 = A0*A2*A3*……An-1；（无A1）

----

Bn-1 = A0*A2*A3*……An-2；（无An-1）

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

二 . 代码实现

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;
    }
}