【leetcode100-016】【数组】除自身以外数组的乘积

发布时间:2023年12月25日

【题干】

给你一个整数数组?nums,返回?数组?answer?,其中?answer[i]?等于?nums?中除?nums[i]?之外其余各元素的乘积?。

题目数据?保证?数组?nums之中任意元素的全部前缀元素和后缀的乘积都在??32 位?整数范围内。

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

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

【思路】

  • 看到不能用除法+O(n),基本上一眼前后缀了,题目给的提示也挺明显的。
  • 进阶提示也给得很明显,让你直接在输出数组操作的意思。
  • 显然,res[i]=nums[i]前缀积*nums[i]后缀积,两轮遍历即可解决问题:
  1. 正向遍历逐个计算当前前缀积,存入res;
  2. 反向遍历逐个计算当前后缀积,和res中的前缀积相乘得到结果;
  3. 考虑边界处理时,想到第i轮中真正需要存入的其实是nums[i-1]的信息,因此将nums[-1]初始化为1(实际操作是将k初始化为1)即可避免单独的边界处理,反向同理。

【题解】

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int k = 1;
        for(int i = 0; i < res.length; i++){
            res[i] = k;
            k = k * nums[i]; // 此时数组存储的是除去当前元素左边的元素乘积
        }
        k = 1;
        for(int i = res.length - 1; i >= 0; i--){
            res[i] *= k; // k为该数右边的乘积。
            k *= nums[i]; // 此时数组等于左边的 * 该数右边的。
        }
        return res;
    }
}

文章来源:https://blog.csdn.net/weixin_63059689/article/details/135122705
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。