238 Product of Array Except Self

238. Product of Array Except Self​
1. Question
Given an array ofn_integers where_n> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].
Solve itwithout divisionand 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 arraydoes notcount as extra space for the purpose of space complexity analysis.)
2. Implementation
(1) DP
1
class Solution {
2
    public int[] productExceptSelf(int[] nums) {
3
        if (nums == null || nums.length == 0) {
4
            return new int[0];
5
        }
6
        int n = nums.length;
7
        int[] res = new int[n];
8
        int[] prodFromLeft = new int[n];
9
​
10
        prodFromLeft[0] = 1;
11
​
12
        for (int i = 1; i < n; i++) {
13
            prodFromLeft[i] = prodFromLeft[i - 1] * nums[i - 1];
14
        }
15
​
16
        int[] prodFromRight = new int[n];
17
        prodFromRight[n - 1] = 1;
18
​
19
        for (int i = n - 2; i >= 0; i--) {
20
            prodFromRight[i] = prodFromRight[i + 1] * nums[i + 1];
21
        }
22
​
23
        for (int i = 0; i < n; i++) {
24
            res[i] = prodFromLeft[i] * prodFromRight[i];
25
        }
26
        return res;
27
    }
28
}
Copied!
(2) Follow up
1
class Solution {
2
    public int[] productExceptSelf(int[] nums) {
3
        if (nums == null || nums.length == 0) {
4
            return new int[0];
5
        }
6
        int n = nums.length;
7
        int[] res = new int[n];
8
        Arrays.fill(res, 1);
9
        int temp = 1;
10
        for (int i = 0; i < n; i++) {
11
            res[i] = temp;
12
            temp *= nums[i];
13
        }
14
​
15
        temp = 1;
16
        for (int i = n - 1; i >= 0; i--) {
17
            res[i] *= temp;
18
            temp *= nums[i];
19
        }
20
        return res;
21
    }
22
}
Copied!
3. Time & Space Complexity
DP: 时间复杂度O(n), 空间复杂度O(n)
Follow up: 时间复杂度O(n), 空间复杂度O(n)

221 Maximal Square

256 Paint House

Last modified 2yr ago

Copy link

Contents

238. Product of Array Except Self

1. Question

2. Implementation

3. Time & Space Complexity

238. Product of Array Except Self​

1. Question

2. Implementation

3. Time & Space Complexity

238. Product of Array Except Self