<p>
238. Product of Array Except Self
Total Accepted: 53516
Total Submissions: 121209
Difficulty: Medium
Given an array of n integers where n > 1,nums
, return an arrayoutput
such thatoutput[i]
is equal to the product of all the elements ofnums
exceptnums[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.)
</p>
<code>
public class ProductofArrayExceptSelf238 {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
int[] valR = new int[res.length];
valR[valR.length-1]=1;
for(int i=valR.length-2;i>=0;--i){//求得该位置的所有右边的数的乘积
valR[i]=nums[i+1]*valR[i+1];
System.out.print(" valR["+i+"]="+valR[i]);
}
System.out.println();
res[0]=1;
for(int i=1;i<res.length;i++){//求得所有左边，并求总乘积
res[i]=res[i-1]*nums[i-1];
System.out.print("--res["+(i-1)+"]="+res[i-1]);
res[i-1] = res[i-1]*valR[i-1];
System.out.print("++res["+(i-1)+"]="+res[i-1]);
}
return res;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ProductofArrayExceptSelf238 pae = new ProductofArrayExceptSelf238();
int[] nums ={1,2,3,4};
int[] result = pae.productExceptSelf(nums);
System.out.println();
for(int i : result){
System.out.print(i+" ");
}
}
}
</code>
