题目
题目描述如下：
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.)
分析
一开始想到的方法是把所有的值乘起来，再依次做除法即可，但是无奈题目中直接注明条件：without division。
想了半天没有想到同时符合两个条件的方法，于是参考了下“Dicuss”，不得不说，对于最高票的答案很服气。How do you get this amazing idea? (摊手)
求解
最高票的方法如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}
}
算法的思路是先从前往后遍历一遍res[]，使得res[]中的第i个元素的值为num[1]到num[i-1]的乘积,然后在从后向前遍历一遍res[]，使得其中的每个元素再乘上num[1+1]到num[n]的值，这样便完成了整个计算。
虽然这个算法看起来不是很复杂，但是我觉得还是比较难想到的。