0238. Product of Array Except Self¶
题目信息¶
- 题号:
0238
- 难度:
Medium
- 主题:
数组、前缀积、后缀积
- 原题:
- 重点:
每个位置排除自身、禁止除法、零与负数、线性时间、输出数组不计入额外空间
题目重述¶
给定整数数组 nums,返回一个与它等长的数组 answer,其中 answer[i] 等于 nums 中除 nums[i] 以外所有元素的乘积。每个输出位置都必须排除当前下标对应的那一个元素,而不是排除所有与它数值相同的元素。
数组长度位于 [2, 10^5],每个元素位于 [-30, 30],并保证任意前缀积或后缀积都适合 32 位有符号整数。解法必须在 O(n) 时间内完成且不能使用除法。进阶要求除返回数组外只使用 O(1) 额外空间;返回数组本身不计入额外空间。
自建示例¶
数组中含一个零:
输入:nums = [3, 0, -2, 5]
输出:[0, -30, 0, 0]
解释:排除零所在位置时,其余元素乘积为 3*(-2)*5=-30;其他位置的乘积都仍包含零。
重复值按位置排除:
输入:nums = [2, 2, 3]
输出:[6, 6, 4]
解释:前两个位置分别只排除自己的那个 2,另一个 2 仍参与乘积。
前缀乘积与后缀乘积¶
answer[i] 可以拆成当前位置左侧所有元素的乘积与右侧所有元素的乘积:
第一遍从左到右,把当前位置的左侧乘积写入 answer[i],再把当前元素乘入滚动的 prefix;
第二遍从右到左,用滚动的 suffix 乘到已有答案上,再更新 suffix。初始化两个滚动乘积为 1,
正好处理数组两端。整个过程不使用除法,因此零元素和多个零元素都会按乘积定义自然得到正确结果。
正确性说明¶
第一遍结束后,answer[i] 等于 nums[0..i-1] 的乘积。第二遍处理 i 时,
suffix 等于 nums[i+1..n-1] 的乘积;相乘后正是排除 nums[i] 的全部元素。
随后把 nums[i] 加入 suffix,不变量推进到下一个更左位置。两遍覆盖所有下标,故每个输出位置都准确排除自身。
C++ 实现¶
class Solution {
public:
std::vector<int> productExceptSelf(std::vector<int>& nums) {
const int n = static_cast<int>(nums.size());
std::vector<int> answer(n, 1);
long long prefix = 1;
for (int i = 0; i < n; ++i) {
answer[i] = static_cast<int>(prefix);
prefix *= nums[i];
}
long long suffix = 1;
for (int i = n - 1; i >= 0; --i) {
answer[i] = static_cast<int>(
static_cast<long long>(answer[i]) * suffix);
suffix *= nums[i];
}
return answer;
}
};
代码分析¶
两次线性扫描,时间复杂度为 O(n);除返回数组外只保存两个乘积,额外空间为 O(1)。
answer 先承载左侧乘积,再原地融合右侧乘积,没有建立完整的前缀表或后缀表;使用 long long
进行乘法中间计算,最终按题目返回类型输出。