当前位置: 首页> 财经> 股票 > 北京设计公司logo_云匠网怎么接单_百度搜索指数1000是什么_ip子域名大全

北京设计公司logo_云匠网怎么接单_百度搜索指数1000是什么_ip子域名大全

时间:2025/7/9 5:51:55来源:https://blog.csdn.net/m0_46464899/article/details/146405307 浏览次数:2次
北京设计公司logo_云匠网怎么接单_百度搜索指数1000是什么_ip子域名大全

这是一道难度为中等的题目,我们来看看题目描述:

给你一个整数数组 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 <= 1 0 5 10^5 105
  • -30 <= nums[i] <= 30
  • 输入 保证 数组 answer[i]32 位 整数范围内

题解

解题思路

  1. 前缀积数组 (prefix):用于存储 nums[i] 左侧所有元素的乘积
  2. 后缀积数组 (suffix):用于存储 nums[i] 右侧所有元素的乘积
  3. 结果数组 (res):最终答案,每个 res[i] 应该等于 nums[i] 左侧所有元素的乘积 × 右侧所有元素的乘积
class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;// 创建前缀积数组 (prefix)int[] prefix = new int[n];prefix[0] = nums[0]; // 第一个前缀积就是 nums[0]for (int i = 1; i < nums.length; i++) {// 当前前缀积等于上一个前缀积乘以当前元素prefix[i] = prefix[i - 1] * nums[i];}// 创建后缀积数组 (suffix)int[] suffix = new int[n];suffix[n - 1] = nums[n - 1]; // 最后一个后缀积就是 nums[n-1]for (int i = n - 2; i >= 0; i--) {// 当前后缀积等于下一个后缀积乘以当前元素suffix[i] = suffix[i + 1] * nums[i];}// 计算最终结果数组 (res)int[] res = new int[n];// 处理边界情况:// res[0] 没有左侧元素,它的结果只由 suffix[1] (即右侧所有元素的乘积) 决定res[0] = suffix[1];// res[n-1] 没有右侧元素,它的结果只由 prefix[n-2] (即左侧所有元素的乘积) 决定res[n - 1] = prefix[n - 2];// 计算中间部分for (int i = 1; i < n - 1; i++) {// 除 nums[i] 自身之外的乘积 = 左侧所有元素的乘积 * 右侧所有元素的乘积res[i] = prefix[i - 1] * suffix[i + 1];}return res;}
}

优化思路

进阶: 你可以在 O(1) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。)

上述代码使用了 两个额外的数组 (prefixsuffix),空间复杂度为 O(n)
我们可以在 O(1) 额外空间(除了返回结果 res 之外)内完成这个任务,优化方法如下:

优化后的解法
  1. 第一遍遍历:直接在 res 数组中存储前缀积。
  2. 第二遍遍历:从右向左遍历,用一个 suffix 变量累乘后缀积,并直接更新 res

代码如下:

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] res = new int[n];// 计算左侧的前缀积res[0] = 1; // 由于要计算除自己以外的乘积,所以左边第一个元素没有前缀,设为 1for (int i = 1; i < n; i++) {res[i] = res[i - 1] * nums[i - 1]; // 乘上左侧的积}// 计算右侧的后缀积,同时直接更新 resint suffix = 1; // 由于要计算除自己以外的乘积,所以右边最后一个元素没有后缀,设为 1for (int i = n - 1; i >= 0; i--) {res[i] *= suffix; // 乘上右侧的积suffix *= nums[i]; // 更新后缀积}return res;}
}

优化后的时间复杂度 & 空间复杂度

  • 时间复杂度:O(n),两次遍历数组
  • 空间复杂度:O(1),除了返回结果数组 res,不使用额外空间

这个方法避免了额外的 prefixsuffix 数组,更加高效!

关键字:北京设计公司logo_云匠网怎么接单_百度搜索指数1000是什么_ip子域名大全

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: