Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4] Output: [24,12,8,6]Note: Please solve it without division and in O(n).
思路
1. from left to right, save each item's left side product
2. from right to left, maintain a variable temp to track each item's right side product, then fill product (left * right) into result
代码
1 class Solution { 2 public int[] productExceptSelf(int[] nums) { 3 int[]dp = new int[nums.length]; 4 5 dp[0] = 1; 6 7 // left to right 8 for( int i = 1; i< nums.length; i++){ 9 dp[i] = dp[i-1] * nums[i-1]; 10 } 11 // right to left 12 int temp = 1; 13 for( int i = nums.length-1; i>=0; i--){ 14 dp[i] = dp[i] *temp; 15 temp = temp*nums[i]; 16 } 17 return dp; 18 19 } 20 }
转载于:https://www.cnblogs.com/liuliu5151/p/9817207.html
