企业网站建设费在会计上,网络认证工程师,电子商务网站后台需求,北京网络推广公司wyhseo【问题描述】[中等]
给你一个长度为 n 的整数数组 nums#xff0c;其中 n 1#xff0c;返回输出数组 output #xff0c;其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。示例:输入: [1,2,3,4]
输出: [24,12,8,6]提示#xff1a;题目数据保证数组之中任…【问题描述】[中等]
给你一个长度为 n 的整数数组 nums其中 n 1返回输出数组 output 其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。示例:输入: [1,2,3,4]
输出: [24,12,8,6]提示题目数据保证数组之中任意元素的全部前缀元素和后缀甚至是整个数组的乘积都在 32 位整数范围内。说明: 请不要使用除法且在 O(n) 时间复杂度内完成此题。进阶
你可以在常数空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组不被视为额外空间。
【解答思路】
1. 左右乘积列表 时间复杂度O(N) 空间复杂度O(N)
class Solution {public int[] productExceptSelf(int[] nums) {int length nums.length;if(length 0) return new int[0];// L 和 R 分别表示左右两侧的乘积列表int[] L new int[length];int[] R new int[length];int[] answer new int[length];// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 0 的元素因为左侧没有元素所以 L[0] 1L[0] 1;for (int i 1; i length; i) {L[i] nums[i - 1] * L[i - 1];}// R[i] 为索引 i 右侧所有元素的乘积// 对于索引为 length-1 的元素因为右侧没有元素所以 R[length-1] 1R[length - 1] 1;for (int i length - 2; i 0; i--) {R[i] nums[i 1] * R[i 1];}// 对于索引 i除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for (int i 0; i length; i) {answer[i] L[i] * R[i];}return answer;}
}
2. 空间复杂度 O(1) 的方法 时间复杂度O(N) 空间复杂度O(1)
class Solution {public int[] productExceptSelf(int[] nums) {int length nums.length;if(length 0) return new int[0];int[] answer new int[length];// answer[i] 表示索引 i 左侧所有元素的乘积// 因为索引为 0 的元素左侧没有元素 所以 answer[0] 1answer[0] 1;for (int i 1; i length; i) {answer[i] nums[i - 1] * answer[i - 1];}// R 为右侧所有元素的乘积// 刚开始右边没有元素所以 R 1int R 1;for (int i length - 1; i 0; i--) {// 对于索引 i左边的乘积为 answer[i]右边的乘积为 Ranswer[i] answer[i] * R;// R 需要包含右边所有的乘积所以计算下一个结果时需要将当前值乘到 R 上R * nums[i];}return answer;}
}
【总结】
1.两种解法代码对比 巧妙借用空间 2.正序逆序相结合的方式思考问题
3.常规做法后压缩空间
转载链接https://leetcode-cn.com/problems/product-of-array-except-self/solution/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode-/
