LeetCode 算法：除自身以外数组的乘积c++
原题链接🔗：除自身以外数组的乘积
难度：中等⭐️⭐️
题目
给你一个整数数组 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) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
题解
左右乘积列表发
- 题解：
理解问题:
- 给定一个长度为
n的整数数组nums，要求返回一个新的数组output，其中每个元素output[i]是nums中除了nums[i]之外所有其他元素的乘积。初始化结果数组:
- 创建一个长度为
n的数组output，并将所有元素初始化为 1。这个数组将存储最终的结果。计算左侧乘积:
- 遍历数组
nums，从左到右，计算每个元素左侧所有元素的乘积，并将结果存储在output数组中。例如，对于nums[0]，左侧没有元素，所以output[0]保持为 1；对于nums[1]，左侧有一个元素
nums[0]，所以output[1]就是nums[0]的值。计算右侧乘积:
- 从数组的右侧开始，从右到左遍历数组
nums，计算每个元素右侧所有元素的乘积。由于左侧乘积已经存储在output中，我们只需要将当前元素的右侧乘积与output[i]相乘即可。更新结果数组:
- 在计算右侧乘积的过程中，由于右侧的乘积是累积的，我们可以使用一个变量
right_product来存储当前元素右侧所有元素的乘积。然后，将这个累积乘积与output[i]相乘，更新output[i]。返回结果数组:
- 完成上述步骤后，
output数组中的每个元素都是原数组中除了它自己之外所有元素的乘积，返回这个数组。优化空间复杂度:
- 如果需要优化到 O(1) 的空间复杂度，可以在原数组上进行操作，但需要谨慎处理，以避免在计算过程中覆盖掉原始数据。
考虑特殊情况:
- 如果数组中存在 0，需要特别注意。因为任何数与 0 相乘都是 0，所以如果数组中有 0，除了 0 所在位置外，其他位置的乘积都将是 0。
编写代码:
- 根据上述思路，编写代码实现算法。
- 复杂度：这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，其中 n 是数组 nums 的长度。这是一个非常高效的解决方案，因为它避免了使用除法，并且只需要一次遍历数组
- 过程：
- 首先，初始化 answer 数组，所有元素都设置为 1。
- 然后，遍历 nums 数组，从左到右计算每个元素左侧的累积乘积，并存储在answer 中
- 接着，初始化 right_product 为 1，并从右到左遍历 nums 数组，计算每个元素右侧的累积乘积，并将这个累积乘积与 answer[i] 相乘，得到最终结果。
- 最后，main 函数中创建 Solution 的实例，调用 productExceptSelf 方法，并打印结果。
- c++ demo：
#include
#include
class Solution {
public:
std::vector<int> productExceptSelf(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> answer(n, 1); // 初始化结果数组，所有元素初始值为1
// 从左到右计算左侧的累积乘积
for (int i = 1; i < n; ++i) {
answer[i] = nums[i - 1] * answer[i - 1];
}
// 从右到左计算右侧的累积乘积
int right_product = 1;
for (int i = n - 2; i >= 0; --i) {
right_product *= nums[i + 1];
answer[i] *= right_product;
}
return answer;
}
};
int main() {
Solution solution;
std::vector<int> nums = {1, 2, 3, 4};
std::vector<int> result = solution.productExceptSelf(nums);
std::cout << "Product of array except self: ";
for (int num : result) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
- 输出结果：
Product of array except self: 24 12 8 6
