# Product of Array Exclude Itself ### Source - lintcode: [(50) Product of Array Exclude Itself](http://www.lintcode.com/en/problem/product-of-array-exclude-itself/) - GeeksforGeeks: [A Product Array Puzzle - GeeksforGeeks](http://www.geeksforgeeks.org/a-product-array-puzzle/) ~~~ Given an integers array A. Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation. Example For A=[1, 2, 3], return [6, 3, 2]. ~~~ ### 題解1 - 左右分治 根據題意，有 result[i]=left[i]?right[i]result[i] = left[i] \cdot right[i]result[i]=left[i]?right[i], 其中 left[i]=∏j=0i?1A[j]left[i] = \prod _{j = 0} ^{i - 1} A[j]left[i]=∏j=0i?1A[j], right[i]=∏j=i+1n?1A[j]right[i] = \prod _{j = i + 1} ^{n - 1} A[j]right[i]=∏j=i+1n?1A[j]. 即將最后的乘積分為兩部分求解，首先求得左半部分的值，然后求得右半部分的值。最后將左右兩半部分乘起來即為解。 ### C++ ~~~ class Solution { public: /** * @param A: Given an integers array A * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] */ vector<long long> productExcludeItself(vector<int> &nums) { const int nums_size = nums.size(); vector<long long> result(nums_size, 1); if (nums.empty() || nums_size == 1) { return result; } vector<long long> left(nums_size, 1); vector<long long> right(nums_size, 1); for (int i = 1; i != nums_size; ++i) { left[i] = left[i - 1] * nums[i - 1]; right[nums_size - i - 1] = right[nums_size - i] * nums[nums_size - i]; } for (int i = 0; i != nums_size; ++i) { result[i] = left[i] * right[i]; } return result; } }; ~~~ ### 源碼分析 一次`for`循環求出左右部分的連乘積，下標的確定可使用簡單例子輔助分析。 ### 復雜度分析 兩次`for`循環，時間復雜度 O(n)O(n)O(n). 使用了左右兩半部分輔助空間，空間復雜度 O(2n)O(2n)O(2n). ### 題解2 - 原地求積 題解1中使用了左右兩個輔助數組，但是仔細瞅瞅其實可以發現完全可以在最終返回結果`result`基礎上原地計算左右兩半部分的積。 ### C++ ~~~ class Solution { public: /** * @param A: Given an integers array A * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] */ vector<long long> productExcludeItself(vector<int> &nums) { const int nums_size = nums.size(); vector<long long> result(nums_size, 1); // solve the left part first for (int i = 1; i < nums_size; ++i) { result[i] = result[i - 1] * nums[i - 1]; } // solve the right part long long temp = 1; for (int i = nums_size - 1; i >= 0; --i) { result[i] *= temp; temp *= nums[i]; } return result; } }; ~~~ ### 源碼分析 計算左半部分的遞推式不用改，計算右半部分的乘積時由于會有左半部分值的干擾，故使用`temp`保存連乘的值。注意`temp`需要使用`long long`, 否則會溢出。 ### 復雜度分析 時間復雜度同上，空間復雜度為 O(1)O(1)O(1).