我一直在leetcode上尝试这个问题。 238.除自身之外的数组的乘积
给定一个整数数组 nums，返回一个数组答案，使得 answer[i] 等于 nums 中除 nums[i].
保证 nums 的任何前缀或后缀的乘积适合 32 位整数。
您必须编写一个在 O(n) 时间内运行且不使用 除法运算。
示例1：
Input: nums = [1,2,3,4] Output: [24,12,8,6]示例2：
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
这是我对上述问题的解决方案。
public int[] productExceptSelf(int[] nums) {
int answer[]=new int[nums.length];
for(int i=0;i<nums.length;i++){
int prod=1;
for(int j=0;j<nums.length;j++){
if(j!=i)
prod=prod*nums[j];
}
answer[i]=prod;
}
return answer;
}
这已通过 19/20 测试用例。有一个测试用例不起作用，我收到错误 “超出时间限制。”
失败的测试用例如下：
Input: [-1,-1,-1,-1,..............]; Output: Time limit exceeded.
如果有人可以帮助我，我必须对我的代码执行什么版本？
我也做leetcode，它给你TLE，因为这不是他们期望的解决方案。它是正确的，但需要 O(N*N) 次运算来计算，有更好的 O(N) 解决方案，
public int[] productExceptSelf(int[] nums) {
int output[] = new int[ nums.length];
output[0] = 1;
// left prefix product
for(int i=1;i<nums.length;i++){
output[i] = output[i-1] * nums[i-1];
}
int product = 1;
for(int i=nums.length-1;i>=0;i--){
output[i] = output[i] * product;
product*= nums[i];
}
return output;
}
该解决方案也给出了 O(N)，但仅使用 1 个周期。
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
res[0] = 1;
res[nums.length-1] = 1;
int n = 1;
int k = nums.length-2;
int fromLeft = 1;
int fromRight = 1;
while(n < nums.length) {
fromLeft = nums[n-1] * fromLeft;
fromRight = nums[k+1] * fromRight;
if (n < k) {
res[n] = fromLeft;
res[k] = fromRight;
} else {
if (n == k) {
res[n] = fromLeft * fromRight;
} else {
res[n] = fromLeft * res[n];
res[k] = fromRight * res[k];
}
}
n++;
k--;
}
return res;
}
上面的问题给出了TLE（Time Limit Exceeds），因为上面的问题是在O(N^2)时间复杂度下解决的。正如问题中提到的，算法应该在 O(N) 时间内运行，并且不使用除法运算符。
方法-1
public int[] productExceptSelf(int[] nums) {
int[] leftProduct = new int[nums.length];
int[] rightProduct = new int[nums.length];
/**
calculate the left Prefix and right Suffix Product.
*/
for (int i=0,j= nums.length-1; i < nums.length; i++, j--) {
if (i == 0) {
leftProduct[i] = nums[i];
rightProduct[j] = nums[j];
}else {
leftProduct[i] = leftProduct[i-1] * nums[i];
rightProduct[j] = rightProduct[j+1] * nums[j];
}
}
for (int i=0; i < nums.length; i++) {
if (i == 0) {
nums[i] = rightProduct[1];
}else if (i == (nums.length - 1)) {
nums[i] = leftProduct[i-1];
}else {
nums[i] = leftProduct[i-1] * rightProduct[i+1];
}
}
return nums;
}
时间复杂度：O(N)， 空间复杂度：O(N)
这也可以在 O(1) 空间中解决（正如提到的输出数组不计为额外空间。）
提示：使用输出数组存储左侧前缀积并从右侧遍历数组。
class Solution {
public int[] productExceptSelf(int[] arr) {
int[] res = new int[arr.length];
for(int i =0, temp =1; i < arr.length;i++){ // first iteration to make res making temp inc
res[i] = temp;
temp *= arr[i];
}
for(int i = arr.length -1 , temp =1;i>=0;i--){
res[i] *= temp;
temp *= arr[i];
}
return res;
}
}
**Time Complexity O(N) Space Complexity O(N)**
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
l=[]
if nums.count(0)>=2:
return [0]*len(nums)
if nums.count(0)==1:
index_of_zero=nums.index(0)
k=nums
s=1
k.remove(0)
for i in range(len(k)):
s=s*k[i]
l=[0]*len(k)
l.insert(index_of_zero,s)
return l
else:
s=1
for i in range(len(nums)):
s=s*nums[i]
for i in range(len(nums)):
l.append(s//nums[i])
return l
我最近收到这个问题。
这就是我在 Java8 中解决它的方法（绝对是在面试之后：p）。
private static List<Integer> getProduct(final int[] inputs) {
int length = inputs.length;
int[] prefixArr = new int[length];
int[] suffixArr = new int[length];
//leftArr
prefixArr[0] = 1;
//rightArr
suffixArr[length - 1] = 1;
for (int index = 1; index < length; index++)
prefixArr[index] = inputs[index - 1] * prefixArr[index - 1];
for (int index = (length - 2); index >= 0; index--)
suffixArr[index] = inputs[index + 1] * suffixArr[index + 1];
return IntStream
.range(0, length)
.mapToObj(index -> prefixArr[index] * suffixArr[index])
.collect(Collectors.toList())
;
}
理想情况下，这可以在 2 个循环和一次流迭代中解决问题，因此满足 O(n)。
我使用python3来解决这个问题，我的代码非常有效，因为我首先计算了前缀和后缀的乘积，然后将两者结合起来。
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
answer = [1] * n
prefix = 1
for i in range(n):
answer[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer