leetcode解题: Product of Array Except Self (238)

发表于 | 分类于

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

解法1：O(N) Time + O(1) Space

把题目分成两个小问题来解决。except self换句话说就是左面的和右面的乘积。
那么从左面扫一遍得到一组数，从右面扫一遍得到一组数。然后把左右两组数相乘便是答案。
一个小要求是需要O(1)的space。在从右面扫描的时候我们不用维护一个数组，而是用一个变量product来记录现在的乘积。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        if (nums == null || nums.length == 0) {
            return nums;
        }
        
        int[] res = new int[nums.length];
        // from left to right
        res[0] = 1;
        for (int i = 1; i < nums.length; ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        
        int product = 1;
        
        // from right to left
        for (int i = nums.length - 1; i >= 0; --i) {
            res[i] = res[i] * product;
            product = product * nums[i];
        }
        
        return res;
    }
}