[LeetCode] Product of Array Except Self

golden_hamster 發(fā)布于2019-08-16 11:14 / 3452人閱讀

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).

Example

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.)

Solution

class Solution {
    public int[] productExceptSelf(int[] nums) {
        long product = 1;
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
        //so there are two special situations: one number or more than one number equals 0
            if (nums[i] != 0) product *= (long) nums[i];
            else {
                //here we consider if one number is 0
                //all other products should be 0
                Arrays.fill(res, 0);
                //*maybe* except for this one, lets create a method for it
                res[i] = getProduct(nums, i);
                //stop here and return, since we already got the correct result array
                //*and* no need to consider the other situation, it would be all 0"s
                return res;
            }
        } 
        for (int i = 0; i < res.length; i++) {
            res[i] = (int) (product / nums[i]);
        }
        return res;
    }
    public int getProduct(int[] nums, int k) {
        int product = 1;
        for (int i = 0; i < nums.length; i++) {
            if (i != k) product *= nums[i];
        }
        return product;
    }
}

Update 2018-9

//Solution without division

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int[] dp = new int[n];
        int[] pd = new int[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1] * nums[i];
        }
        pd[n-1] = nums[n-1];
        for (int i = n-2; i > 0; i--) {
            pd[i] = pd[i+1] * nums[i];
        }
        res[0] = pd[1];
        res[n-1] = dp[n-2];
        for (int i = 1; i < n-1; i++) {
            res[i] = dp[i-1] * pd[i+1];
        }
        return res;
    }
}