leetcode238-除自身以外数组的乘积

原题

给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4] 输出: [24,12,8,6]

提示: 题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。

说明:不要使用除法,且在 O(n) 时间复杂度内完成此题。

进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

解法

思想

顺序相反的两次遍历

代码

func productExceptSelf(nums []int) []int {
    lsum := make([]int, len(nums))
    rsum := make([]int, len(nums))
    ans := make([]int, len(nums))
    for index := 0; index < len(nums); index++{
        if index == 0{
            lsum[index] = 1
        } else {
            lsum[index] = lsum[index-1] * nums[index-1]
        }
    }
    for index := len(nums) - 1; index >= 0; index--{
        if index == len(nums) - 1{
            rsum[index] = 1
        } else {
            rsum[index] = rsum[index+1] * nums[index+1]
        }
    }
    for index := 0; index < len(nums); index++{
        ans[index] = lsum[index] * rsum[index]
    }
    return ans
}

优化后:(减少空间复杂度,用ans代替lsum,用临时变量代替rsum)

func productExceptSelf(nums []int) []int {
    length := len(nums)
    answer := make([]int, length)

    // answer[i] 表示索引 i 左侧所有元素的乘积
    // 因为索引为 '0' 的元素左侧没有元素, 所以 answer[0] = 1
    answer[0] = 1
    for i := 1; i < length; i++ {
        answer[i] = nums[i-1] * answer[i-1]
    }

    // R 为右侧所有元素的乘积
    // 刚开始右边没有元素,所以 R = 1
    R := 1
    for i := length - 1; i >= 0; i-- {
        // 对于索引 i,左边的乘积为 answer[i],右边的乘积为 R
        answer[i] = answer[i] * R
        // R 需要包含右边所有的乘积,所以计算下一个结果时需要将当前值乘到 R 上
        R *= nums[i]
    }
    return answer
}

java:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        ans[0] = 1;
        for(int i = 1;i<nums.length;i++){
            ans[i] = ans[i-1]*nums[i-1];
        }
        int prev = nums[nums.length-1];
        for(int i = nums.length-2;i>=0;i--){
            ans[i] = prev*ans[i];
            prev = prev*nums[i];
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode238-%e9%99%a4%e8%87%aa%e8%ba%ab%e4%bb%a5%e5%a4%96%e6%95%b0%e7%bb%84%e7%9a%84%e4%b9%98%e7%a7%af/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月3日
下一篇 2020年6月5日

相关推荐

  • leetcode494-目标和

    原题 给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。…

    算法 2019年12月12日
    090
  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗…

    算法 2019年12月18日
    0150
  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示: 你可以假定这些字符串都是格式良好的: 字符串非空 字符…

    算法 2020年1月28日
    02260
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0110
  • leetcode264-丑数II

    原题 编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, …

    算法 2020年2月10日
    0190
  • leetcode300-最长上升子序列

    原题 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10…

    算法 2020年3月14日
    0250
  • 蓝桥杯试题-大小写转换

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   输入一个字符串,将大写字符变成小写、小写变成大写,然后输出 输入格式 acbAB 输出格式 ACBab …

    算法 2020年2月29日
    080
  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    090
  • leetcode994-腐烂的橘子

    原题 在给定的网格中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜…

    2020年3月4日
    0100
  • leetcode17-电话号码的字母组合

    原题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入: "23" 输出: …

    2020年5月3日
    0130

发表回复

登录后才能评论