LeetCode : 238. Product of Array Except Self 数组除了本身的乘积

àì夳堔傛蜴生んèń 2021-06-24 16:11 232阅读 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;
        }
    }