除了自身以外数组的乘积238. 除了自身以外数组的乘积https://leetcode.cn/problems/product-of-array-except-self/给你一个整数数组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输入保证数组answer[i]在32 位整数范围内解法1左右两边相乘时间O(n)空间2O(n)class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint l(n,0),ans(n,0); vectorint r(n,0); for(int i0;in;i) { if(i0)l[i]nums[i]; else l[i]l[i-1]*nums[i]; } for(int in-1;i0;i--) { if(in-1)r[i]nums[i]; else r[i]r[i1]*nums[i]; } for(int i0;in;i) { if(i0)ans[i]r[i1]; else if(in-1)ans[i]l[i-1]; else ans[i]l[i-1]*r[i1]; } return ans; } };解法2利用一个数组降低空间复杂度class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint ans(n,0); for(int i0;in;i) { if(i0)ans[i]1; else ans[i]ans[i-1]*nums[i-1]; } int r; for(int in-1;i0;i--) { if(in-1)r1; else rr*nums[i1]; ans[i]*r; } return ans; } };缺失的第一个正数41. 缺失的第一个正数https://leetcode.cn/problems/first-missing-positive/给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。示例 1输入nums [1,2,0]输出3解释范围 [1,2] 中的数字都在数组中。示例 2输入nums [3,4,-1,1]输出2解释1 在数组中但 2 没有。示例 3输入nums [7,8,9,11,12]输出1解释最小的正数 1 没有出现。提示1 nums.length 10^5-2^31 nums[i] 2^31 - 1如何利用数组本身的空间来记录“哪些正整数已经出现过了”。因为题目要求O(n) 时间和常数级别的额外空间我们不能新建一个哈希表只能“就地改造”原数组。即原地哈希算法核心思路对于一个长度为n的数组缺失的第一个正数只可能出现在[1, n1]这个范围内。如果1 ~ n都出现了答案就是n1。否则答案就是1 ~ n中没有出现的最小的那个数。所以问题转化为如何在不使用额外空间的前提下快速检查1 ~ n中的每个数是否在数组里方法一标记法这个方法把数组改造成一个“正负号哈希表”清理无效数据把所有 0的数改成n1一个不影响结果的“大数”这样数组里全是正数。用负号做标记遍历数组对于每个数取绝对值后x如果它在1 ~ n范围内就把数组中下标为x-1的位置的值标记为负数。关键为什么能放心地改为负数因为后续遍历时我们通过abs()取出它原本的数值仍然可以继续用作下标去标记其他位置。负号只表示“这个下标对应的数字已经出现过”而数值本身绝对值被完整保留继续发挥作用。检查结果遍历数组找到第一个值大于 0的位置该位置的下标i对应的数字i1就是缺失的最小正数。如果全部是负数返回n1。这种方法非常巧妙但需要你理解“用绝对值保留原始信息用符号表示状态”的思想。方法二置换法思路更直观把每个数放到它“应该出现”的位置上。对于数组中的数x如果它在[1, n]范围内那么它“应该”出现在下标为x-1的位置。我们遍历数组对于每个位置i不断将nums[i]与它应该在的位置nums[nums[i]-1]交换直到nums[i]不在[1, n]范围内或者它已经处于正确的位置。最后第一个nums[i] ! i1的位置i对应的i1就是缺失的数如果全都对得上返回n1。这个方法像“归位排序”最多交换n次也满足时空要求。官方解法1标记法hit对于长度为n的数组答案的范围在[ 1 , n1 ]之间将非正数的值修改为n1对于在[ 1 n1 ]之间的数字x通过将idx x-1的位置上的数字变为负数来标识 x 的存在扫描数组如果idx位置出现了非负数则说明idx1这个数字没有出现即为答案class Solution { public: int firstMissingPositive(vectorint nums) { int nnums.size(); for(int i0;in;i) { if(nums[i]0) nums[i]n1; } for(int i0;in;i) { int valabs(nums[i]); if(valn) { nums[val-1]-abs(nums[val-1]); //不修改绝对值只修改正负从而标记val是否出现 } } for(int i0;in;i) { if(nums[i]0) return i1; } return n1; } };
LeetCode热题-除了自身以外数组的乘积 缺失的第一个正数
发布时间：2026/6/26 4:13:13
除了自身以外数组的乘积238. 除了自身以外数组的乘积https://leetcode.cn/problems/product-of-array-except-self/给你一个整数数组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输入保证数组answer[i]在32 位整数范围内解法1左右两边相乘时间O(n)空间2O(n)class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint l(n,0),ans(n,0); vectorint r(n,0); for(int i0;in;i) { if(i0)l[i]nums[i]; else l[i]l[i-1]*nums[i]; } for(int in-1;i0;i--) { if(in-1)r[i]nums[i]; else r[i]r[i1]*nums[i]; } for(int i0;in;i) { if(i0)ans[i]r[i1]; else if(in-1)ans[i]l[i-1]; else ans[i]l[i-1]*r[i1]; } return ans; } };解法2利用一个数组降低空间复杂度class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint ans(n,0); for(int i0;in;i) { if(i0)ans[i]1; else ans[i]ans[i-1]*nums[i-1]; } int r; for(int in-1;i0;i--) { if(in-1)r1; else rr*nums[i1]; ans[i]*r; } return ans; } };缺失的第一个正数41. 缺失的第一个正数https://leetcode.cn/problems/first-missing-positive/给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。示例 1输入nums [1,2,0]输出3解释范围 [1,2] 中的数字都在数组中。示例 2输入nums [3,4,-1,1]输出2解释1 在数组中但 2 没有。示例 3输入nums [7,8,9,11,12]输出1解释最小的正数 1 没有出现。提示1 nums.length 10^5-2^31 nums[i] 2^31 - 1如何利用数组本身的空间来记录“哪些正整数已经出现过了”。因为题目要求O(n) 时间和常数级别的额外空间我们不能新建一个哈希表只能“就地改造”原数组。即原地哈希算法核心思路对于一个长度为n的数组缺失的第一个正数只可能出现在[1, n1]这个范围内。如果1 ~ n都出现了答案就是n1。否则答案就是1 ~ n中没有出现的最小的那个数。所以问题转化为如何在不使用额外空间的前提下快速检查1 ~ n中的每个数是否在数组里方法一标记法这个方法把数组改造成一个“正负号哈希表”清理无效数据把所有 0的数改成n1一个不影响结果的“大数”这样数组里全是正数。用负号做标记遍历数组对于每个数取绝对值后x如果它在1 ~ n范围内就把数组中下标为x-1的位置的值标记为负数。关键为什么能放心地改为负数因为后续遍历时我们通过abs()取出它原本的数值仍然可以继续用作下标去标记其他位置。负号只表示“这个下标对应的数字已经出现过”而数值本身绝对值被完整保留继续发挥作用。检查结果遍历数组找到第一个值大于 0的位置该位置的下标i对应的数字i1就是缺失的最小正数。如果全部是负数返回n1。这种方法非常巧妙但需要你理解“用绝对值保留原始信息用符号表示状态”的思想。方法二置换法思路更直观把每个数放到它“应该出现”的位置上。对于数组中的数x如果它在[1, n]范围内那么它“应该”出现在下标为x-1的位置。我们遍历数组对于每个位置i不断将nums[i]与它应该在的位置nums[nums[i]-1]交换直到nums[i]不在[1, n]范围内或者它已经处于正确的位置。最后第一个nums[i] ! i1的位置i对应的i1就是缺失的数如果全都对得上返回n1。这个方法像“归位排序”最多交换n次也满足时空要求。官方解法1标记法hit对于长度为n的数组答案的范围在[ 1 , n1 ]之间将非正数的值修改为n1对于在[ 1 n1 ]之间的数字x通过将idx x-1的位置上的数字变为负数来标识 x 的存在扫描数组如果idx位置出现了非负数则说明idx1这个数字没有出现即为答案class Solution { public: int firstMissingPositive(vectorint nums) { int nnums.size(); for(int i0;in;i) { if(nums[i]0) nums[i]n1; } for(int i0;in;i) { int valabs(nums[i]); if(valn) { nums[val-1]-abs(nums[val-1]); //不修改绝对值只修改正负从而标记val是否出现 } } for(int i0;in;i) { if(nums[i]0) return i1; } return n1; } };
