专栏首页WeiMLing剑指Offer的学习笔记(C#篇)-- 构建乘积数组

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer的学习笔记(C#篇)-- 栈的压入、弹出序列

    做好此题的关键在于读懂题目的意思,做了部分题目后发现,该题属于一个不易理解的题目,现在用俗话来解释一下。两个内容是一样,但顺序不同的序列,其中一...

    WeiMLing
  • 剑指Offer的学习笔记(C#篇)-- 数组中重复的数字

    给数组搞内外两个循环,第一个循环是把数组的每一个数都遍历出来,而第二个循环是,除了第一个数组正在遍历的那个数以外的数进行查找,找到和他一样的,就...

    WeiMLing
  • 剑指Offer的学习笔记(C#篇)-- 二叉树的下一个节点(好理解版本)

    该题目我们可以借鉴一个非常影响不好的例子来理解题意(重男轻女的思想,当然本人可不会这样,本人家庭更不会,从小被姐姐打成哈士奇)。

    WeiMLing
  • LeetCode 905. 按奇偶排序数组

    905. 按奇偶排序数组: https://leetcode-cn.com/problems/sort-array-by-parity/

    村雨遥
  • Android高级动画(1)

    动画在移动App开发中的重要性不言而喻,通俗点讲,动画可以让我们的App界面不那么死板,可以带来酷炫的交互效果,用Material Design专业点的说法,动...

    大公爵
  • 聊聊细节 - 你知道缓存的正确打开方式么?(2)

    当我们通过一些方式:如后台管理系统更新了相关的数据信息,或者用户在一些操作的时候更新了一些数据信息,如果这些信息正好也在缓存里,那一般也需要在更新数据库的时候,...

    桶哥
  • Guava 指南 之「通用 Object 方法」

    通用 Object 方法 equals 当你的对象含有的多个字段可能为null的时候,实现Object.equals会很痛苦,因为你不得不分别对它们进行null...

    CG国斌
  • 最长重复子数组

    ​ 模板题直接上dp,dp[i] [j] 为A数组以 i 结尾,B数组以 j 结尾的最长公共子串长度。

    你的益达
  • PyQT 入门(1):程序基础框架

    http://www.cnblogs.com/answeryi/archive/2012/09/27/2705860.html

    bear_fish
  • Python数据分析师养成记

    从这周开始,罗罗攀开始更新新系列《Python数据分析师养成记》。该系列将以小白的视角出发,一步步的进阶Python数据分析。

    罗罗攀

扫码关注云+社区

领取腾讯云代金券