leetcode：238. 除自身以外数组的乘积

题目

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

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

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

示例：

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

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

本题同：
[中等] 剑指 Offer 66. 构建乘积数组

解答 & 代码

image.png

  1. class Solution {
  2. public:
  3.     vector<int> productExceptSelf(vector<int>& nums) {
  4.         int len = nums.size();
  5.         vector<int> answer(len, 1);
  6.           // 正向遍历 nums 数组以计算下三角
  7.         for(int i = 1; i < len; ++i)
  8.             answer[i] = answer[i - 1] * nums[i - 1];
  9.           // 逆向遍历 nums 数组以计算上三角
  10.         int prod = 1;
  11.         for(int i = len - 2; i >= 0; --i)
  12.         {
  13.             prod *= nums[i + 1];
  14.             answer[i] *= prod;
  15.         }
  16.         return answer;
  17.     }
  18. };

复杂度分析：设 nums 数组包含 n 个数

  • 时间复杂度 O(n)：正向、逆向两次遍历 nums 数组
  • 空间复杂度 O(1)：题目中说输出数组不视为额外空间复杂度，因此空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：12 ms, 在所有 C++ 提交中击败了 98.63% 的用户
  4. 内存消23.5 MB, 在所有 C++ 提交中击败了 53.58% 的用户