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