品牌网站建设小蝌蚪1a,北京网站设计制作教程,WordPress仿制,做电影网站配什么公众号优质博文#xff1a;IT-BLOG-CN
一、题目
给你一个整数数组nums#xff0c;返回数组answer#xff0c;其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32位整数范围内。请不要使用除法#xff0…优质博文IT-BLOG-CN
一、题目
给你一个整数数组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)的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组 不被视为 额外空间。
二、代码
【1】创建左右乘积列表 我们不能将所有数字的乘积除以给定索引处的数字得到相应的答案而是利用索引左侧所有数字的乘积和右侧所有数字的乘积即前缀与后缀相乘得到答案。初始化两个数组Left和Right对于指定的下表ileft[i]代表i左侧所有数据的乘积right[i]代表i右侧所有数据的乘积。我们利用循环将数据填充到lfet[]和right[]数组中然后将left[i]和right[i]相乘就是i的左右乘积。
class Solution {public int[] productExceptSelf(int[] nums) {if (nums null || nums.length 0) {return null;}// 我们使用数组也就是当前数字的left[] 和 right[] 数组分别存储左右两边的和;int len nums.length;int res[] new int[len];int left[] new int[len];int right[] new int[len];// 第一个数之前的数的乘积为1所以先给个默认值left[0] 1;for (int i 1; i len; i) {// left 中保存的是i之前所有数的乘积left[i] left[i - 1] * nums[i - 1];}// 最有边的数也保存为1right[len - 1] 1;for (int i len - 2; i 0; i--) {right[i] right[i 1] * nums[i 1];}for (int i 0; i len; i) {res[i] left[i] * right[i];}return res;}
}时间复杂度 O(N)其中N指的是数组nums的大小。预处理L和R数组以及最后的遍历计算都是O(N)的时间复杂度。 空间复杂度 O(N)其中N指的是数组nums的大小。使用了L和R数组去构造答案L和R数组的长度为数组nums的大小。
【2】空间复杂度O(1)的方法 由于输出数组不算在空间复杂度内那么我们可以将L或R数组用输出数组来计算。先把输出数组当作L数组来计算然后再动态构造R数组得到结果。
class Solution {public int[] productExceptSelf(int[] nums) {if (nums null || nums.length 0) {return null;}// 因为返回的数组可以不算在空间复杂度中所以可以作为临时变量存放left[]数据int len nums.length;int res[] new int[len];// // 第一个数之前的数的乘积为1所以先给个默认值res[0] 1;for (int i 1; i len; i) {// left 中保存的是i之前所有数的乘积res[i] res[i - 1] * nums[i - 1];}// 然后从后向前变量通过变量 right保存前几位数的乘积int right 1;for (int i len - 1; i 0; i--) {res[i] * right;// 放在返回值的后面就相当于i 1right * nums[i];} return res;}
}时间复杂度 O(N)其中N指的是数组nums的大小。分析与方法一相同。 空间复杂度 O(1)输出数组不算进空间复杂度中因此我们只需要常数的空间存放变量。
