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

文章目录

写在前面
Tag
题目来源
题目解读
解题思路
- 方法一：记录左右乘积
- 空间优化
写在最后

写在前面

本专栏专注于分析与讲解【面试经典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;}
};

复杂度分析

时间复杂度： $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;}
};