題目
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].
解析
給定一個整數(shù)數(shù)組，求每個位置上鞭莽，除了這個位置上的數(shù)的其他數(shù)的乘積。
第一遍就AC且是discuss中最高票答案還是很開心的麸祷，這一題要求不用除法且O(n)時間復(fù)雜度澎怒，讓我想到了前兩天看的動態(tài)規(guī)劃中的前向和后向思想：
分兩次遍歷：
第一次從左到右遍歷，得到某個位置上所有左邊數(shù)的乘積（前向）
第二次從右到左遍歷阶牍，得到某個位置上所有右邊數(shù)的乘積（后向）
二者一乘即為結(jié)果喷面。
基于這種思想，可以用一個數(shù)組output保存前向的結(jié)果走孽，再用一個變量保存按位后向的結(jié)果惧辈，每掃描一位就更新output對應(yīng)位置上的值。當(dāng)然掃描的第一位的值為1磕瓷。
代碼
public int[] productExceptSelf(int[] nums) {
int[] output = new int[nums.length];
output[0] = 1;
//計算前向乘積
for(int i = 1; i < nums.length; ++i){
output[i] = output[i - 1] * nums[i - 1];
}
//計算后向乘積
int k = 1;
for(int i = nums.length - 1; i >= 0; --i){
output[i] *= k;
k = k * nums[i];
}
return output;
}