导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-238.Product of Array Except Self

题目

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

翻译

给出一个由n个整数组成的数组nums,n>1,返回一个output数组,使得output[i]等于nums中除nums[i]之外所有元素的乘积。
不用除法在O(n)内解决本题。
例如,给出 [1,2,3,4] ,返回 [24,12,8,6]
跟进:
你能否在常数空间复杂度下解决本题?(分析空间复杂度时output数组不算做额外空间。)

先从左向右遍历,使得对于output中每个数output[i],都等于nums[1]到nums[i - 1]的乘积。
再从右向左遍历,设一个tmp值,对于每个output[i],tmp等于nums[nums.length - 1]到nums[i + 1]的乘积,output[i]与tmp相乘,即得所得:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length, tmp = 1;
int[] output = new int[len];
output[0] = 1;

for (int i = 1; i < len; i++)
output[i] = output[i - 1] * nums[i - 1];

for (int i = len - 1; i >= 0; i--) {
output[i] *= tmp;
tmp *= nums[i];
}

return output;
}
}

参考:
https://leetcode.com/discuss/46104/simple-java-solution-in-o-n-without-extra-space