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

其他系列文章导航

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 作为返回值，不计入复杂度考虑）。

---