【数据结构和算法】除自身以外数组的乘积

2023-12-14 15:31:31

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

三、代码

四、复杂度分析


前言

这是力扣的238题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的两种。


一、题目描述

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

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

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

示例 1:

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

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证?数组?nums之中任意元素的全部前缀元素和后缀的乘积都在??32 位?整数范围内

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


二、题解

思路与算法:

本题的难点在于 不能使用除法 ,即需要 只用乘法 生成数组 ans 。根据题目对 ans[i] 的定义,可列出下图所示的表格。

根据表格的主对角线(全为 1?),可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积,即可不使用除法就获得结果。

下图中?A=nums ,?B=ans。

流程:

  1. 初始化:数组 ans?,其中 ans[0]=1 ;辅助变量 tmp=1 。
  2. 计算 ans[i] 的 下三角 各元素的乘积,直接乘入 ans[i] 。
  3. 计算 ans[i] 的 上三角 各元素的乘积,记为 tmp ,并乘入 ans[i] 。
  4. 返回 ans 。

补充:

见下图就知道了:

原数组:       [1       2       3       4]
左部分的乘积:   1       1      1*2    1*2*3
右部分的乘积: 2*3*4    3*4      4      1
结果:        1*2*3*4  1*3*4   1*2*4  1*2*3*1

从上面的图可以看出,当前位置的结果就是它左部分的乘积再乘以它右部分的乘积。因此需要进行两次遍历,第一次遍历用于求左部分的乘积,第二次遍历在求右部分的乘积的同时,再将最后的计算结果一起求出来。


三、代码

Java版本:?

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

C++版本:?

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return vector<int>();
        vector<int> ans(len);
        ans[0] = 1;
        int tmp = 1;
        for (int i = 1; i < len; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }
        for (int i = len - 2; i >= 0; i--) {
            tmp *= nums[i + 1];
            ans[i] *= tmp;
        }
        return ans;
    }
};

Python版本:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        if length == 0:
            return []
        ans = [1] * length
        tmp = 1
        for i in range(1, length):
            ans[i] = ans[i - 1] * nums[i - 1]
        for i in range(length - 2, -1, -1):
            tmp *= nums[i + 1]
            ans[i] *= tmp
        return ans

四、复杂度分析

  • 时间复杂度 O(N) : 其中 N?为数组长度,两轮遍历数组 nums ,使用 O(N) 时间。
  • 空间复杂度 O(1) : 变量 tmp 使用常数大小额外空间(数组 ans 作为返回值,不计入复杂度考虑)。

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