Product of Array Exclude Itself

Question

  1. Given an integers array A.
  3. Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation.
  5. Example
  6. For A=[1, 2, 3], return [6, 3, 2].

题解1 - 左右分治

根据题意，有 result[i] = left[i] \cdot right[i], 其中 left[i] = \prod {j = 0} ^{i - 1} A[j], right[i] = \prod {j = i + 1} ^{n - 1} A[j]. 即将最后的乘积分为两部分求解，首先求得左半部分的值，然后求得右半部分的值。最后将左右两半部分乘起来即为解。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: Given an integers array A
  5.      * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
  6.      */
  7.     vector<long long> productExcludeItself(vector<int> &nums) {
  8.         const int nums_size = nums.size();
  9.         vector<long long> result(nums_size, 1);
  10.         if (nums.empty() || nums_size == 1) {
  11.             return result;
  12.         }
  14.         vector<long long> left(nums_size, 1);
  15.         vector<long long> right(nums_size, 1);
  16.         for (int i = 1; i != nums_size; ++i) {
  17.             left[i] = left[i - 1] * nums[i - 1];
  18.             right[nums_size - i - 1] = right[nums_size - i] * nums[nums_size - i];
  19.         }
  20.         for (int i = 0; i != nums_size; ++i) {
  21.             result[i] = left[i] * right[i];
  22.         }
  24.         return result;
  25.     }
  26. };

源码分析

一次for循环求出左右部分的连乘积，下标的确定可使用简单例子辅助分析。

复杂度分析

两次for循环，时间复杂度 O(n). 使用了左右两半部分辅助空间，空间复杂度 O(2n).

题解2 - 原地求积

题解1中使用了左右两个辅助数组，但是仔细瞅瞅其实可以发现完全可以在最终返回结果result基础上原地计算左右两半部分的积。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: Given an integers array A
  5.      * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
  6.      */
  7.     vector<long long> productExcludeItself(vector<int> &nums) {
  8.         const int nums_size = nums.size();
  9.         vector<long long> result(nums_size, 1);
  11.         // solve the left part first
  12.         for (int i = 1; i < nums_size; ++i) {
  13.             result[i] = result[i - 1] * nums[i - 1];
  14.         }
  16.         // solve the right part
  17.         long long temp = 1;
  18.         for (int i = nums_size - 1; i >= 0; --i) {
  19.             result[i] *= temp;
  20.             temp *= nums[i];
  21.         }
  23.         return result;
  24.     }
  25. };

源码分析

计算左半部分的递推式不用改，计算右半部分的乘积时由于会有左半部分值的干扰，故使用temp保存连乘的值。注意temp需要使用long long, 否则会溢出。

复杂度分析

时间复杂度同上，空间复杂度为 O(1).