LeetCode : 238. Product of Array Except Self 数组除了本身的乘积 àì夳堔傛蜴生んèń 2021-06-24 16:11 236阅读 0赞 **试题** Given an array nums of n integers where n > 1, return an array output such that output\[i\] is equal to the product of all the elements of nums except nums\[i\]. Example: Input: \[1,2,3,4\] Output: \[24,12,8,6\] Note: Please solve it without division and in O(n). Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.) **代码** 这一题要求不能超过O(n),这也就意味着我们只能遍历一次或者几次。而反观计算方法会发现i位置的乘积为其左边累积积和右边累积积的乘积。那我们可以把左右累积积都存在数组里。 class Solution { public int[] productExceptSelf(int[] nums) { int len = nums.length; int[] smul = new int[len]; int[] emul = new int[len]; int[] res = new int[len]; int stmp = 1; int etmp = 1; for(int i=0; i<len; i++){ stmp *= nums[i]; etmp *= nums[len-1-i]; smul[i] = stmp; emul[len-1-i] = etmp; } for(int i=0; i<len; i++){ if(i==0) res[i] = emul[i+1]; else if(i==len-1) res[i] = smul[len-2]; else res[i] = smul[i-1] * emul[i+1]; } return res; } } 优化版: class Solution { public int[] productExceptSelf(int[] nums) { int len = nums.length; int[] smul = new int[len]; int[] emul = new int[len]; int[] res = new int[len]; smul[0] = 1; emul[len-1] = 1; for(int i=1; i<len; i++){ smul[i] = nums[i-1]*smul[i-1]; } for(int i=len-2; i>=0; i--){ emul[i] = nums[i+1]*emul[i+1]; } for(int i=0; i<len; i++){ res[i] = smul[i] * emul[i]; } return res; } } 更强的版本是,你在向右遍历时存储左边部分累积积,然后向左遍历时乘以右边部分累积积。 class Solution { public int[] productExceptSelf(int[] nums) { // The length of the input array int length = nums.length; // Final answer array to be returned int[] answer = new int[length]; // answer[i] contains the product of all the elements to the left // Note: for the element at index '0', there are no elements to the left, // so the answer[0] would be 1 answer[0] = 1; for (int i = 1; i < length; i++) { // answer[i - 1] already contains the product of elements to the left of 'i - 1' // Simply multiplying it with nums[i - 1] would give the product of all // elements to the left of index 'i' answer[i] = nums[i - 1] * answer[i - 1]; } // R contains the product of all the elements to the right // Note: for the element at index 'length - 1', there are no elements to the right, // so the R would be 1 int R = 1; for (int i = length - 1; i >= 0; i--) { // For the index 'i', R would contain the // product of all elements to the right. We update R accordingly answer[i] = answer[i] * R; R *= nums[i]; } return answer; } }
还没有评论,来说两句吧...