网站开发大致多少钱,公司网站的具体的建设方案,域名注册网站源码,国际新闻视频https://leetcode.cn/problems/product-of-array-except-self/description/
一、题目分析
给你一个整数数组 nums#xff0c;返回 数组 answer #xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀…https://leetcode.cn/problems/product-of-array-except-self/description/
一、题目分析
给你一个整数数组 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] 结合题目以及示例我们不难看出今天这道题目的需要完成的操作就是求出除自身以外的乘积并存放到一个数组中最后返回数组。
三、解题思路代码实现 在拿到任何一道题目的时候我们首先要做的就是认真审题读懂题目要求以后在心里或者草稿纸上写出模拟过程的伪代码之后再做进一步的优化。今天这道题目也一样我们什么算法都先不要考虑就用最暴力的方法来做。
1、暴力解法复杂度为O(n^2)
1、核心思路对于每一个nums[i]遍历整个数组跳过nums[i]并计算其余元素的乘积 2、关键步骤 1、初始化ans数组该数组的长度于nums数组相同 2、双重循环计算乘积 外层循环遍历每个nums[i]准备计算ans[i]。 内层循环遍历nums所有元素遇到 i j时跳出此次循环排除自身其余元素累乘到sum。 3、存储结果 将计算好的sum存入到ans[i]中。
vectorint productExceptSelf(vectorint nums) {vectorint ans(nums.size()); // 定义结果数组长度与 nums 相同// 遍历计算每个位置 ans[i] 的值for (int i 0; i nums.size(); i) {long long sum 1; // 初始化乘积为 1因为 1 不影响乘法结果// 计算 nums 中除 nums[i] 外所有元素的乘积for (int j 0; j nums.size(); j) {if (j i) continue; // 跳过当前元素 nums[i]不参与乘积计算sum * nums[j]; // 累乘其他元素}ans[i] sum; // 将计算结果存入 ans[i]}return ans; // 返回最终结果
} 但是本题暴力解法是并不能通过所有的测试用例题目的数据范围给到了1e5如果是双重循环的话就是1e10。(PS:C/C 1秒能跑的数据大概是在1e7~1e8左右)。 那么现在就要想办法优化把这段程序优化至O(n)
2、分类讨论数学分类法 数学分类法的核心思路 首先要统计出数组中是否有零如果有的话零有多少个如果有且仅有一个的话那么ans数组中的元素就应该是除nums数组元素中为0的那一个元素应该为其余元素的乘积其他元素则全部为零。 如果nums数组中0的个数1那么ans数组中的所有元素都应为0 除以上两种情况外 也就是nums数组中没有零。
单零情况若数组中仅含一个零那么结果数组中零所在位置的元素为其余非零元素的乘积其余位置元素均为零。例如对于数组 [1, 0, 2, 3]结果数组为 [0, 6, 0, 0]因为 1*2*36零位置填充该值其余位置补零。多零情况当数组中零的数量大于 1 时无论如何计算乘积必然为零因此结果数组的所有元素均为零。无零情况若数组中不存在零结果数组的每个元素等于数组所有元素的乘积除以对应位置的元素。例如对于数组 [1, 2, 3, 4]结果数组为 [24, 12, 8, 6] 因为 1*2*3*424分别除以 1、2、3、4 得到对应位置结果。
class Solution {
public:vectorint productExceptSelf(vectorint nums) {// 初始化结果数组大小与输入数组相同vectorint ans(nums.size());// sum: 所有元素的乘积初始为1// cnt_0: 统计数组中0的个数int sum 1, cnt_0 0;// 第一次遍历计算所有元素的乘积并统计0的个数for (auto i : nums) {sum * i; // 累乘所有元素if (i 0) // 遇到0时计数cnt_0;}// 情况1数组中恰好有1个0if (cnt_0 1) {int sum 1; // 重新计算非0元素的乘积避免之前sum0的影响// 计算所有非0元素的乘积for (int i 0; i nums.size(); i) {if (nums[i] ! 0)sum * nums[i];}// 填充结果数组// - 非0位置的结果为0因为总乘积含0// - 0位置的结果为非0元素的乘积for (int i 0; i nums.size(); i) {if (nums[i] ! 0)ans[i] 0;elseans[i] sum;}return ans;}// 情况2数组中有超过1个0// 所有位置的结果都是0因为任何位置都至少包含一个0if (cnt_0 1) {return ans; // ans已初始化为全0}// 情况3数组中没有0// 直接计算ans[i] 总乘积 / nums[i]for (int i 0; i nums.size(); i) {ans[i] sum / nums[i];}return ans;}
}; 以上代码是优化了时间复杂度但是题目中也是有明确要求不能使用除法的所以尽管我们这段代码的时间复杂度已经优化至O(n)。但还是需要改进。
3、前缀和后缀和思想正解√ 核心思想 此方法的核心思想就是空间换时间利用前缀和的思想的对ans数组进行预处理这样的好处就是每次取一个结果所需的时间复杂度为常数级也就是O(1)。 其次通过将目标乘积拆分为两部分左部分、右部分。第一次看到这段代码时候应该会想为什么能把nums[i]排除呢 左边乘积ans[i]不包含 nums[i]因为只乘到 nums[i-1]。 右边乘积right不包含 nums[i]因为先乘 right再更新 right。 最终结果ans[i] 左边乘积 × 右边乘积自然排除了 nums[i]。 class Solution {
public:vectorint productExceptSelf(vectorint nums) {// 初始化结果数组所有元素初始值为1乘法单位元vectorint ans(nums.size(), 1);// 第一次遍历计算每个元素左边所有元素的乘积前缀积// ans[i] 表示 nums[0] × nums[1] × ... × nums[i-1]for (int i 1; i nums.size(); i) {ans[i] ans[i - 1] * nums[i - 1]; // 递推计算前缀积}// 初始化右边乘积为1最右边元素的右边没有元素int right 1;// 第二次遍历从右往左计算右边乘积并合并到结果中// 此时 ans[i] 左边乘积 × 右边乘积for (int i nums.size() - 1; i 0; i--) {ans[i] * right; // 将当前元素的右边乘积乘到结果上right * nums[i]; // 更新右边乘积包含当前元素}return ans;}
}; 至此上述代码均满足题目的所有要求完结撒花
四、题目总结 本题要求在不使用除法且时间复杂度为 O(n) 的条件下计算数组中除自身元素之外其余各元素的乘积。解题过程需结合题目要求与数据限制通过逐步优化算法来实现目标。 在暴力解法中采用双重循环遍历数组对每个元素计算其余元素的乘积虽然逻辑直观但时间复杂度高达 O(n^2)无法满足题目数据范围的要求。 数学分类法通过统计数组中零的数量进行分类讨论优化了时间复杂度至 O(n)。当数组中有一个零结果数组中零位置为其余非零元素乘积其余位置为零若有多个零结果数组全为零若无零则用所有元素乘积除以对应位置元素得到结果。然而该方法使用了除法运算不符合题目要求。 最终的前缀和与后缀和思想是本题正解。利用空间换时间通过两次遍历分别计算前缀积和后缀积将目标乘积拆分为左右两部分。先从前向后计算前缀积存入结果数组再从后向前更新后缀积并与前缀积合并既避免了除法运算又满足了 O(n) 的时间复杂度要求高效且准确地解决了问题 。这种解题过程体现了在算法设计中平衡时间复杂度、空间复杂度与题目限制条件的重要性。 算法之美在于其严谨的逻辑与精巧的设计。希望读者能通过本题掌握空间换时间的核心思想在日后的开发中灵活运用这种预处理技巧。谢谢大家荆轲刺秦
