普通数组-----除了自身以外数组的乘积

🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

<<Git>><<MySQL>>

🌟心向往之行必能至

题目解析

这道题的核心是在不使用除法、且时间复杂度为O(n)的前提下，计算数组中每个元素除自身外所有元素的乘积。

直接暴力计算每个位置的乘积会导致O(n²)的时间复杂度，无法满足题目要求。我们可以利用前缀和后缀乘积的思路来高效解决这个问题。

思路分析

1. 前缀乘积数组v1

   • v1[i]表示nums[0]到nums[i-1]的乘积
   • 例如，v1[0] = 1（没有前缀元素），v1[1] = nums[0]，v1[2] = nums[0] * nums[1]

2. 后缀乘积数组v2

   • v2[i]表示nums[i+1]到nums[n-1]的乘积
   • 例如，v2[n-1] = 1（没有后缀元素），v2[n-2] = nums[n-1]

3. 结果计算

   • 对于每个位置i，除自身外的乘积就是v1[i] * v2[i]

完整代码

cpp

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> v1(n, 1); vector<int> v2(n, 1); // 计算前缀乘积 for (int i = 1; i < n; ++i) { v1[i] = v1[i-1] * nums[i-1]; } // 计算后缀乘积 for (int i = n-2; i >= 0; --i) { v2[i] = v2[i+1] * nums[i+1]; } // 计算结果 vector<int> ret(n); for (int i = 0; i < n; ++i) { ret[i] = v1[i] * v2[i]; } return ret; } };

复杂度分析

• 时间复杂度：O(n)
  • 我们只进行了三次线性遍历，分别计算前缀乘积、后缀乘积和最终结果。
• 空间复杂度：O(n)
  • 主要来自前缀和后缀两个辅助数组。
  • 可以优化到 O (1) 额外空间：直接在结果数组上先计算前缀乘积，再反向遍历计算后缀乘积并累积。

优化思路（O (1) 额外空间）

我们可以把结果数组先作为前缀乘积数组，然后用一个变量动态维护后缀乘积，从而去掉v2数组，将空间复杂度降为 O (1)。

cpp

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> ret(n, 1); // 前缀乘积存入结果数组 for (int i = 1; i < n; ++i) { ret[i] = ret[i-1] * nums[i-1]; } // 动态维护后缀乘积并更新结果 int suffix = 1; for (int i = n-1; i >= 0; --i) { ret[i] *= suffix; suffix *= nums[i]; } return ret; } };