【LeetCode-238】除自身以外数组的乘积(Product of Array Except Self)

题目描述

给定长度为 $n$ 的整数数组 $nums$，其中 $n>1$，返回输出数组 $output$，其中 $output[i]$ 等于 $nums$ 中除 $nums[i]$ 之外其余各元素的乘积。
示例:

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
不考虑乘法int溢出问题。

解法1：若可以使用除法

解法步骤：

C++代码

class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		int n = nums.size();
		vector<int> result;
		int nums_0 = 0;
		int index_0 = -1;
		int product = 1;
		for (int i = 0; i < n; ++i) {
			if (nums[i] != 0) {
				product *= nums[i];
			}
			else{
				++nums_0;
				if (nums_0 > 1){
					result.resize(n, 0);
					return result;
				}
				index_0 = i;
				continue;
			}
		}
		if (nums_0 != 0){
			result.resize(n, 0);
			result[index_0] = product;
		}
		else{
			result.resize(n);
			for (int i = 0; i < n; ++i){
				result[i] = product / nums[i];
			}
		}
		return result;
	}
};

Python代码

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        result = []
        nums_0 = 0
        index_0 = -1
        product = 1
        for i in range(n):
            if nums[i] != 0:
                product *= nums[i]
            else:
                nums_0 += 1
                if nums_0 > 1:
                    result = [0 for _ in range(n)]
                    return result
                index_0 = i
                continue
        result = [0 for _ in range(n)]
        if nums_0 != 0:
            result[index_0] = product
        else:
            for i in range(n):
                result[i] = product // nums[i]
        return result

解法2：O(n) 时间复杂度，维护左积、右积数组

乘法满足结合律：$a\ast b\ast c\ast d\ast e=(a\ast b)\ast c\ast (d\ast e)$，也就是说，每个位置上的结果等于它的左积乘上右积
因此，我们可以维护两个数组，第一个数组记录每个位置上其左边所有数的乘积，第二个数组记录其右边所有数的乘积。

C++代码

class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		int n = nums.size();
		vector<int> result(n);
		vector<int> left_product(n);
		vector<int> right_product(n);
		left_product[0] = nums[0];
		right_product[n - 1] = nums[n-1];
		for (int i = 1; i < n; ++i) {
			left_product[i] = nums[i] * left_product[i - 1];
			right_product[n - 1 - i] = nums[n - 1 - i] * right_product[n - i];
		}
		result[0] = right_product[1];
		result[n - 1] = left_product[n - 2];
		for (int i = 1; i < n-1; ++i) {
			result[i] = left_product[i - 1] * right_product[i + 1];
		}
		return result;
	}
};

Python代码

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        result = [0 for _ in range(n)]
        left_product = [1 for _ in range(n)]
        right_product = [1 for _ in range(n)]
        left_product[0] = nums[0]
        right_product[n - 1] = nums[n - 1]
        for i in range(1, n):
            left_product[i] = nums[i] * left_product[i - 1]
            right_product[n - 1 - i] = nums[n - 1 - i] * right_product[n-i]
        result[0] = right_product[1]
        result[n - 1] = left_product[n - 2]
        for i in range(1, n-1):
            result[i] = left_product[i - 1] * right_product[i + 1]
        return result

解法3：O(n) 时间复杂度，常数空间复杂度

要保证常数空间复杂度，则除结果数组外不能包含其他数组，即要想办法舍去解法2中的左积、右积数组。
首先，我们可以省去结果数组，将结果存放在右积数组中，如下图所示，右积数组中第一个位置的值$$right[0]=input[0]\ast right[1]$$
其结果就是result[0]。接下来，我们可以让$result[1]=right[1]=left[0]\ast right[2]$，即让右积数组保存结果数组的值，从而省去了一个数组空间。

1. 顺序循环计算左积数组。
2. 用变量right保存右积数组的当前值。
3. 逆序循环，计算当前的右积值和结果值即可。
   

C++代码

class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		int n = nums.size();
		vector<int> left_product(n);
		left_product[0] = nums[0];
		int right = nums[n-1];
		for (int i = 1; i < n-1; ++i) {
			left_product[i] = nums[i] * left_product[i - 1];
		}
		left_product[n - 1] = left_product[n - 2];
		for (int i = n-2; i > 0; --i) {
			left_product[i] = left_product[i - 1] * right;
			right *= nums[i];
		}
		left_product[0] = right;
		return left_product;
	}
};

Python代码

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        left_product = [1 for _ in range(n)]
        left_product[0] = nums[0]
        right = nums[n-1]
        for i in range(1, n-1):
            left_product[i] = nums[i] * left_product[i - 1]
        left_product[n - 1] = left_product[n - 2]
        for i in range(n-2, 0, -1):
            left_product[i] = left_product[i - 1] * right
            right *= nums[i]
        left_product[0] = right
        return left_product