Product of Array Except Self

Problem:
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Analysis:
The single result can be achieved by preProduct left X preProduct right. 
[1, 2, 3, 4], the left product array is [1, 1, 2, 6]. Remember the left[i] is the product from nums[0] to nums[i - 1]. 

Solution:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0)
            return nums;
        int[] left = new int[nums.length];
        left[0] = 1;
        int right = 1;
        
        for (int i = 1; i < nums.length; i++) {
            left[i] = left[i - 1] * nums[i - 1]; 
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            left[i] *= right;
            right *= nums[i];
        }

        return left;
    }
}

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array