首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Leetcode 题目解析之 Product of Array Except Self

Leetcode 题目解析之 Product of Array Except Self

原创
作者头像
ruochen
发布2022-01-09 11:43:59
发布2022-01-09 11:43:59
1.4K0
举报

Given an array of n integers where n > 1, nums, return an array output such that outputi is equal to the product of all the elements of nums except numsi.

Solve it without division and in O(n).

For example, given 1,2,3,4, return 24,12,8,6.

Follow up:

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

可以定义两个辅助数组,left和right。

lefti:存放numsi之前的乘积

righti:存放numsi之后的乘积

但是分析一下,空间可以优化,因为我们先从右向左算,再从左向右算,只需要返回的那一个数组就够了。

代码语言:txt
复制
    public int[] productExceptSelf(int[] nums) {
        int[] rt = new int[nums.length];
        rt[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            rt[i] = rt[i + 1] * nums[i+1];
        }
        int left = 1;
        for (int i = 0; i < nums.length; i++) {
            rt[i] *= left;
            left *= nums[i];
        }
        return rt;
    }

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档