【面试经典150 | 数组】除自身以外数组的乘积

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【数组】

---

题目来源

面试经典150 | 238. 除自身以外数组的乘积

---

题目解读

给你一个数组 nums，求出每个元素在数组这个集合中补集的乘积，以数组的形式返回答案。

要求：不准使用除法。

---

解题思路

题目要求不准使用除法，如果可以使用除的话，我们可以计算数组中所有元素的乘积，然后除以相应的数值即可得到答案数组。

既然不能使用除法，我们就老老实实的乘，将每个数左右两侧的数一个一个的乘起来，但是如果不做预处理的话时间复杂度为 $O(n^2)$，对于本题的数据量一定超时，因此可以先记录每个位置左、右侧的元素乘积。

方法一：记录左右乘积

我们维护两个数组 L、R 分别记录每个位置左、右侧的所有元素乘积。具体地，L[i] 表示下标 i 左侧所有元素之积，初始 L[0] = 1；R[i] 表示下标 i 右侧所有元素之积，初始 R[n-1] = 1，$n$ 为数组 nums 的长度：

• 枚举 i = 1 到 i = n-1，更新 L[i] = nums[i-1] * L[i-1]；
• 枚举 i = n-2 到 i = 1，更新 R[i] = nums[i+1] * R[i+1]。

最后，枚举 i = 0 到 i = n-1，更新 ret[i] = L[i] * R[i]，返回 ret。

实现代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> L(n, 0), R(n, 0);
        L[0] = 1;
        for (int i = 1; i < n; ++i) {
            L[i] = nums[i-1] * L[i-1];
        }

        R[n-1] = 1;
        for (int i = n -2; i >= 0; --i) {
            R[i] = R[i+1] * nums[i+1];
        }

        vector<int> res(n);
        for (int i = 0; i < n; ++i) {
            res[i] = L[i] * R[i];
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 nums 的长度。

空间复杂度：$O(n)$。

空间优化

有一个地方可以优化一下，我们只用一个数组 ret 记作为答案数组，又做为记录每个位置左侧所有元素乘积的数组。

还是 枚举 i = 1 到 i = n-1，更新 ret[i] = nums[i-1] * ret[i-1]；接下来用一个变量 R 来记录当前位置后面所有元素的乘积，初始化 R = 1。我们从后往前更新最后的答案数组，ret[i] *= R，然后对 R 进行更新 R *= nums[i]。

这样可以节省一个数组空间。

实现代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n);
        ret[0] = 1;
        for (int i = 1; i < n; ++i) {
            ret[i] = nums[i-1] * ret[i-1];
        }

        int R = 1;
        for (int i = n-1; i >= 0; --i) {
            ret[i] *= R;
            R *= nums[i];
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 nums 的长度。

空间复杂度：$O(1)$，使用的答案数组不算做额外的空间。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。