剑指offer系列之五十:构建乘积数组

简介:

题目描述

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

在代码中已经给出了此题的解题思路,直接看代码(已被牛客AC):

package com.rhwayfun.offer;

public class ConstructMultipleArray {

    /**
     * 基本思路是把前半部分与后半部分的结果保存到不同的数组中
     * @param A
     * @return
     */
    public int[] multiply(int[] A) {
        int n = A.length;
        //front[i]就是从A[0]...到A[i - 1]的值
        int[] front = new int[n];
        //异常处理
        if(n <= 1) return front;
        /* back[i]就是从A[i + 1]...到A[n - 1]的值
         * back数组的第一位从最后一位开始,所以back[n - 1]=1
         */
        int[] back = new int[n];
        front[0] = back[n - 1] = 1;
        //分别计算前半部分与后半部分的值,并分别将结果保存在front与back数组中
        for(int i = 1; i < n; i++){
            front[i] = front[i - 1] * A[i - 1];
            back[n - 1 - i] = back[n - i] * A[n - i];
        }
        //将两个计算结果再次相乘得到最后的结果
        for(int i = 0; i < n; i++){
            front[i] *= back[i];
        }
        //返回的front数组即为所求
        return front;
    }


    public static void main(String[] args) {
        int[] A ={1,2,3,4};
        int[] r = new ConstructMultipleArray().multiply(A);
        for (int i : r) {
            System.out.print(i + " ");
        }
    }
}
AI 代码解读
目录
打赏
0
0
0
0
85
分享
相关文章
【LeetCode-每日一题】-378. 有序矩阵中第K小的元素
【LeetCode-每日一题】-378. 有序矩阵中第K小的元素
【斐波那契数组篇】妙解熟知的斐波那契问题(毫无压力版)
【斐波那契数组篇】妙解熟知的斐波那契问题(毫无压力版)
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
【一刷《剑指Offer》】面试题 9:斐波那契数列(扩展:青蛙跳台阶、矩阵覆盖)
【一刷《剑指Offer》】面试题 9:斐波那契数列(扩展:青蛙跳台阶、矩阵覆盖)
每日一题《剑指offer》数组篇之构建乘积数组
每日一题《剑指offer》数组篇之构建乘积数组
53 0
每日一题《剑指offer》数组篇之构建乘积数组
每日一题——除自身以外数组的乘积
每日一题——除自身以外数组的乘积
【剑指offer】-构建乘积数组-42/67
【剑指offer】-构建乘积数组-42/67
代码随想录算法训练营第二十二天 | LeetCode 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树
代码随想录算法训练营第二十二天 | LeetCode 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树
66 0
代码随想录训练营Day2:1.有序数组的平方 2.长度最小的子数组3,螺旋矩阵
代码随想录训练营Day2:1.有序数组的平方 2.长度最小的子数组3,螺旋矩阵
33 0
代码随想录算法训练营第二天| 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结
代码随想录算法训练营第二天| 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等