LeetCode238：乘积除自身的高效解法

LeetCode238

给你一个整数数组nums，返回 数组answer，其中answer[i]等于nums中除了nums[i]之外其余各元素的乘积 。

题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。

请不要使用除法，且在O(n)时间复杂度内完成此题。

示例 1:

输入:nums =[1,2,3,4]

输出:[24,12,8,6]

示例 2:

输入:nums = [-1,1,0,-3,3]
输出:[0,0,9,0,0]

Python解法

1.双数组

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: length = len(nums) L, R, res = [0]*length, [0]*length, [0]*length L[0] = 1 for i in range(1, length): L[i] = nums[i - 1] * L[i - 1] R[length - 1] = 1 for i in reversed(range(length - 1)): R[i] = nums[i + 1] * R[i + 1] for i in range(length): res[i] = L[i] * R[i] return res

2.优化

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) res = [1] * n # 左指针：计算左侧乘积 left = 1 for i in range(n): res[i] = left left *= nums[i] # 右指针：计算右侧乘积并相乘 right = 1 for j in range(n - 1, -1, -1): res[j] *= right right *= nums[j] return res

Java解法

1.双数组

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

2.优化

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

C++解法

1.双数组

#include <vector> using namespace std; class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int length = nums.size(); vector<int> L(length, 0); vector<int> R(length, 0); vector<int> res(length, 0); L[0] = 1; for (int i = 1; i < length; ++i) { L[i] = nums[i - 1] * L[i - 1]; } R[length - 1] = 1; for (int i = length - 2; i >= 0; --i) { R[i] = nums[i + 1] * R[i + 1]; } for (int i = 0; i < length; ++i) { res[i] = L[i] * R[i]; } return res; } };

2.优化

#include <vector> using namespace std; class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> res(n, 1); int left = 1; for (int i = 0; i < n; ++i) { res[i] = left; left *= nums[i]; } int right = 1; for (int j = n - 1; j >= 0; --j) { res[j] *= right; right *= nums[j]; } return res; } };