给出一个数组 nums[i](i = 0,1,...,n-1) 输出数组output[i]满足 output[i] = nums[0] * num[1] * num[2] *..*num[i-1] * num[i+1]*... *num[n-1]
要求不能使用除了output之外的大内存，满足时间复杂度O(n), 空间复杂度O(1)。
分析下我们可以令dpf[i] = nums[0] * num[1] * num[2] *..*num[i-1] 而 dpb[i] = num[i+1]*... *num[n-1];
而output[i] = dpf[i] * dpb[i]；dpd[i]可以在作为常数mul出现，而dpf[i]可以预存在 output[i]中。
注意：当n=1时的判断。
1 class Solution { 2 public: 3 std::vector<int> productExceptSelf(std::vector<int>& nums) { 4 std::vector<int> output(nums.size(), 1); 5 if(nums.size() == 1) return nums; 6 for(std::vector<int>::size_type i = 1; i < nums.size(); ++i){ 7 output[i] *= output[i-1] * nums[i -1]; 8 } 9 int mul = 1; 10 for(int i = nums.size() - 2 ; i >= 0 ; --i){ 11 mul *= nums[i + 1]; 12 output[i] *= mul; 13 } 14 return output; 15 } 16 };
Leetcode 238 Product of Array Except Self 递推
原文：http://www.cnblogs.com/onlyac/p/5135996.html