题解 | #牛群重量积#

牛群重量积

https://www.nowcoder.com/practice/d3c6930f140f4b7dbf3a53dd36742193

知识点:数组 前缀和

思路:不让使用除法,又需要是on复杂度,那就使用前缀和吧

前缀和基本思想:利用累加和将计算区间和的复杂度从on降低到o1

这题需要用前缀和后缀两个数组

首先理解一下前缀和后缀和,比如要求一个数组除自己之外的乘积,

那么前缀和以及后缀和都是差值少村一个自身,比如求3,那么前缀和,就是1*2 后缀和就是 4*5,显而易见,相乘就是

除去自身以外的乘积。

那么题目要求除去自身之外,还要求自身的前后两个;那么只需要改版一下即可。

还是3,那么前缀取对应前一个数,存储的是1,后缀存储取对应后一个数,存储的是5,排除 2 3 4

编程语言:java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型一维数组
     */
    public int[] productExceptSelf (int[] nums) {
        // write code here
        int pre[] = new int[nums.length + 2];
        int post[] = new int[nums.length + 2];
        pre[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        post[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            post[i] = post[i + 1] * nums[i + 1];
        }

        int result[] = new int[nums.length];
        for (int i = 0; i < result.length; i++) {
            //处理边界
            if (i - 1 < 0)
                result[i] = pre[i] * post[i + 1];
            if (i + 1 >= nums.length)
                result[i] = pre[i - 1] * post[i];
            if (i - 1 >= 0 && i + 1 < nums.length)
                result[i] = pre[i - 1] * post[i + 1];
        }
        return result;
    }
}

全部评论

相关推荐

frutiger:逆天,我家就安阳的,这hr咋能说3k的,你送外卖不比这工资高得多?还说大厂来的6k,打发叫花子的呢?这hr是怎么做到说昧良心的话的
找工作时遇到的神仙HR
点赞 评论 收藏
分享
见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务