【LeetCode-中等题】238. 除自身以外数组的乘积

这篇具有很好参考价值的文章主要介绍了【LeetCode-中等题】238. 除自身以外数组的乘积。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

【LeetCode-中等题】238. 除自身以外数组的乘积,力扣,# 中等题,leetcode,python,算法

题解一:暴力双指针—超时了

双指针暴力查找(需考虑begin == end 和begin == end ==i) 的情况 ----- 力扣示例超出时间限制

    public   int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int begin = 0;
        int end = length -1;
        int i = 0;
        int[] number = new int[length];
        int sum = 1;
        while(i<length){
            if (begin == i) {
                begin++;
                continue;
            }
            if (end == i) {
                end--;
                continue;
            }
            if (begin < end) {
                sum *= nums[begin]*nums[end];
                begin ++ ;
                end -- ;
            }else if(begin == end){
                number[i] =sum * nums[begin] ;
                begin =0;
                end = length -1;
                i++;
                sum =1;
                continue;
            }else if(begin > end ){
                number[i] =sum;
                begin =0;
                end = length -1;
                i++;
                sum =1;
                continue;
            }
        }
        return number;
    }

题解二:左右乘积之积

【LeetCode-中等题】238. 除自身以外数组的乘积,力扣,# 中等题,leetcode,python,算法

方法二: 左右乘积之积 = 除自身以外数组的乘积  分别计算左右乘积再最后相乘
    public   int[] productExceptSelf(int[] nums) {
        //  1 2 3 4
        // (1*2)3 4       3------>  前缀积(1*2) * 4后缀积
        int length = nums.length;
        // L 和 R 分别表示左右两侧的乘积列表
        int[] left = new int[length];
        int[] right = new int[length];
        //计算左前缀乘积
        // L[i] 为索引 i 左侧所有元素的乘积
        // 对于索引为 '0' 的元素,因为左侧没有元素,所以 L[0] = 1
        left[0] = 1;
        for(int i=1 ;i< length ;i++){
            left[i] = nums[i-1]  * left[i-1];
        }
       
        // R[i] 为索引 i 右侧所有元素的乘积
        // 对于索引为 'length-1' 的元素,因为右侧没有元素,所以 R[length-1] = 1

        right[length -1] = 1;
        for(int i=length-2 ;i>= 0 ;i--){
         right[i] = nums[i + 1] * right[i +1];
        }
        // 对于索引 i,除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        int[] answaer = new int[length];
        for(int i =0;i<length;i++){
            answaer[i] = right[i] * left[i];
        }
        return answaer;
    }

题解三:左右乘积之积 —优化空间复杂度(O(1))

相比较上面的做法,使用最终答案数组代替其中一个缀积,然后再计算缀积相乘的时候,使用一个累乘变量来记录某一个前缀和,最后只开辟了一个数组来存最终答案,复杂度为O(1)文章来源地址https://www.toymoban.com/news/detail-672979.html



// 方法三: 优化左右乘积之积   使得最后答案数组提前存储 前缀或后缀之积,这样就可以减少开辟一个数组 降低空间复杂度
    public   int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素, 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
			}
        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素,所以 R = 1
        int R = 1;
    for (int i = length - 1; i >= 0; i--) {
        // 对于索引 i,左边的乘积为 answer[i],右边的乘积为 R
        answer[i] = answer[i] * R ;
        // R 需要包含右边所有的乘积,所以计算下一个结果时需要将当前值乘到 R 上
        R = R *nums[i]; //同步记录下一个元素的前缀和
    }
    return answer;
    }
}

到了这里,关于【LeetCode-中等题】238. 除自身以外数组的乘积的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 238. 除自身以外数组的乘积 --力扣 --JAVA

    给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。 请不要使用除法,且在 O(n) 时间复杂度内完成此题。 最简单的是把所有元素相乘

    2024年02月08日
    浏览(37)
  • 238. 除自身以外数组的乘积

    给你一个整数数组 nums ,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请**不要使用除法,**且在 O(*n*) 时间复杂度内完成此题。 示例 1: 示例 2: 提示:

    2024年02月10日
    浏览(37)
  • 【前缀和】238. 除自身以外数组的乘积

    前缀与后缀的思路 对于给定索引i,将它左边的所有数字乘积乘以右边所有数字的乘积 初始化两个数组L R 计算L[i] = L[i - 1] * nums[i - 1] 也就是左侧所有数字的乘积 计算R[i] = R[i + 1] * nums[i + 1] 也就是右侧所有数字的成绩 计算L[I] * R[i]

    2024年02月15日
    浏览(36)
  • 【LeetCode】替换空格&&消失的数字&&分割链表&&除自身以外数组的乘积

    ​🌠 作者:@阿亮joy. 🎆 专栏: 《阿亮爱刷题》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 请实现一个函数,把字符串 s 中的每个空格替换成\\\"%20\\\"。 示例 1: 输入: s = \\\"We are happy.\\\" 输出: \\\"We%20are%2

    2024年02月22日
    浏览(35)
  • 算法---除自身以外数组的乘积

    给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请不要使用除法,且在 O(n) 时间复杂度内完成此题。 示例 1: 输入: nums = [1,2,3,4]

    2024年02月16日
    浏览(31)
  • 除自身以外数组的乘积(c语言详解)

            给你一个整数数组 nums ,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法 ,且在 O(n) 时间复杂度内完成此题。 提示:  2 =

    2024年02月10日
    浏览(39)
  • 【C语言】每日一题(除自身以外数组的乘积)

    添加链接描述,链接奉上 暴力循换真的是差生法宝,简单好懂,就是不实用,大多数的题目都会超过时间限制(无奈) 思路: 1.写一个除自身的数组乘积函数 2.利用 for循环遍历数组 , i 作为循环变量,当遍历到 i 时,就求出除 i 以外的数组乘积 3.放入返回数组中 代码实现

    2024年02月10日
    浏览(38)
  • 283.除自身以外数组的乘积(前缀积、C解法)

    给你一个整数数组  nums ,返回 数组  answer  ,其中  answer[i]  等于  nums  中除  nums[i]  之外其余各元素的乘积  。 题目数据 保证 数组  nums 之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。 请  不要使用除法, 且在  O( n ) 时间复杂度内完成此题。 示

    2024年01月23日
    浏览(39)
  • 算法——前缀和之除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和

    这几道题对于我们前面讲过的一维、二维前缀和进行了运用,包含了面对特殊情况的反操作 目录 4.除自身以外数组的乘积 4.1解析 4.2题解 5.和为K的子数组 5.1解析 5.2题解 6.和可被K整除的子数组 6.1解析 6.2题解 7.连续数组 7.1题解 7.2题解 8.矩阵区域和 8.1解析 8.2题解 4.除自身以外

    2024年04月14日
    浏览(43)
  • leetcode 152. 乘积最大子数组

    题目链接:leetcode 152 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 1)示例 1: 输入: nums = [2,3,-2,4] 输出: 6 解释: 子数

    2024年02月03日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包